[database] 정렬 된 문자열 테이블 (SSTable) 또는 B + 트리 데이터베이스 인덱스?


1 Answers

Tokutek 에서 사용되는 프랙탈 트리는 데이터베이스의 더 나은 색인이라고 생각합니다. B- 트리보다 실제 20 배에서 80 배 향상된 기능을 제공합니다.

프랙탈 트리 인덱스가 here 어떻게 작동하는지에 대한 훌륭한 설명이 here .

Question

이 예제를 설명하기 위해 두 개의 데이터베이스를 사용합니다 : CouchDB and Cassandra .

CouchDB

CouchDB는 문서 인덱스에 대해 B + Tree를 사용합니다 (추가 전용 환경에서 작동 하도록 영리한 수정 사용). 특히 문서가 수정 (삽입 / 업데이트 / 삭제) 될 때 실행중인 데이터베이스 파일과 전체 리프에 추가됩니다. -> 문서 바로 다음에 업데이트 된 개정에 의해 영향을받는 모든 노드의 B + 트리에서 노드 경로.

이 조각 모음 식 색인 개정은 수정 사항과 함께 바로 인라인되어 전체 색인은 파일 끝에 추가 된 가장 최근의 색인 수정과 데이터 파일의 뒷부분에있는 추가 조각이 아직 관련이 있고 ' 아직 수정되지 않았습니다.

B + 트리 검색은 O (logn)입니다.

카산드라

카산드라는 레코드 키를 테이블에 저장하고 (이 질문에 대한 배열로 생각합시다) 때때로 개별 정렬 된 정렬 된 문자열 테이블 로 기록합니다.

우리는이 모든 테이블의 콜렉션을 "인덱스"(내가 이해 한 것)라고 생각할 수 있습니다.

카산드라는 이러한 정렬 된 문자열 테이블 을 수시로 압축 / 결합 하여 인덱스의 파일 표현을보다 완벽하게 작성해야합니다.

정렬 된 배열을 검색 하는 것은 O (logn)입니다.

문제

CassDB에서 부분 B + 트리 청크를 유지하는 것과 Cassandra에서 부분 정렬 된 문자열 인덱스를 유지하는 것 사이에 비슷한 수준의 복잡성이 있다고 가정하고 둘 다 O (logn) 검색 시간을 제공하면 데이터베이스 인덱스를 더 잘 표현할 수 있다고 생각합니까? ?

특별히 흥미로운 구현 세부 사항이있는 경우 특히 궁금합니다. 또는 둘 다 씻어 내고 개발자가 더 선호하는 데이터 구조를 선택하면됩니다.

생각해 줘서 고마워.




각 접근법에 대해 언급해야 할 몇 가지 사항은 다음과 같습니다.

B- 나무

  • 읽기 / 쓰기 작업은 로그 O(logn) 로 가정됩니다. 그러나 단일 데이터베이스 쓰기는 스토리지 시스템에서 다중 쓰기로 이어질 수 있습니다 . 예를 들어, 노드가 가득차면 분할되어야하며 이는 2 개의 새 노드에 2 개의 쓰기가 있고 부모 노드를 업데이트하기위한 1 개의 추가 쓰기가 있음을 의미합니다. 부모 노드가 가득차면 어떻게 증가 할 수 있는지 확인할 수 있습니다.
  • 일반적으로 B- 트리는 각 노드가 페이지 크기를 갖는 방식으로 저장됩니다. 이로 인해 쓰기 증폭 이라는 현상이 발생합니다. 단일 바이트를 업데이트해야하는 경우에도 전체 페이지가 기록됩니다.
  • 쓰기는 대개 무작위 (순차적이지 않음)이며, 따라서 자기 디스크의 경우 특히 느립니다 .

SSTables

  • SSTables는 일반적으로 다음 접근 방식에서 사용됩니다. Memtable이라는 메모리 내 구조가 있습니다. 가끔씩이 구조는 디스크에 SSTable로 플러시됩니다. 결과적으로 모든 쓰기가 memtable로 이동하지만 읽기가 현재 memtable에 없을 수도 있습니다.이 경우 현재 SSTables에서 검색됩니다 .
  • 결과적으로 쓰기는 O(logn) 입니다. 그러나 항상 메모리에서 수행된다는 것을 명심하십시오. 따라서 B- 디스크 디스크의 로그 연산보다 훨씬 빠른 속도로 수행해야합니다. 완전을 기하기 위해, 쓰기는 응급 복구를위한 write-ahead 로그에도 기록됩니다. 그러나 이것들은 모두 순차적 쓰기이므로 B- 트리의 임의 쓰기보다 훨씬 효율적 입니다.
  • memtable의 메모리에서 제공 될 경우 읽기 속도가 훨씬 빨라질 것으로 예상됩니다 . 그러나 오래된 디스크 기반 SSTable을 살펴볼 필요가있을 때 잠재적으로 B- 트리보다 읽기 속도가 느려질 수 있습니다. SSTable에 디스크 읽기를 수행하지 않고 값이 들어 있는지 확인하기 위해 블룸 필터 사용과 같은 몇 가지 최적화가 있습니다.
  • 앞서 언급했듯이 SSTables를 병합하는 데 사용되는 압축 이라고하는 백그라운드 프로세스가 있습니다. 이렇게하면 삭제 된 값을 제거하고 조각화를 방지 할 수 있지만 상당한 쓰기로드가 발생하여 들어오는 작업의 쓰기 처리량에 영향을 줄 수 있습니다.

그것이 분명해 짐에 따라,이 두 접근법의 비교는 훨씬 더 복잡합니다. 구체적인 비교를 제공하기위한 매우 단순한 시도에서 나는 다음과 같이 말할 수 있다고 생각한다.

  • SSTables는 B- 트리보다 쓰기 처리량이 훨씬 좋습니다. 그러나, 그들은 계속되는 다짐 때문에 덜 안정된 행동을 할 것으로 예상됩니다. 이 벤치마킹 비교 에서는 예가 표시됩니다.
  • B-tree는 일반적으로 트랜잭션 의미론이 필요한 유스 케이스에 우선합니다. 이것은 각 키가 단일 장소에서만 발견 될 수 있기 때문입니다 (SSTable과 달리 일부 SSTable에서는 폐기 된 값이있는 SSTable에 존재할 수 있음). 또한 일부 키는 값의 범위를 값의 일부로 나타낼 수 있기 때문에 가능합니다. 나무. 즉, 키 수준 및 범위 수준 잠금 메커니즘을 쉽게 수행 할 수 있습니다.

참고 문헌

[1] LevelDB와 MySQL의 성능 비교

[2] 데이터 집약적 인 응용 프로그램 설계




Related