B+나무 그리고 LSM 트리 우리가 빌딩 블록에 대해 이야기할 때 두 가지 기본 데이터 구조가 있습니다. 데이터베이스. B+ 트리는 검색 및 삽입 시간이 덜 필요한 경우에 사용되는 반면, LSM 트리는 쓰기 집약적인 데이터 세트가 있고 읽기가 그다지 높지 않은 경우에 사용됩니다.
이 기사에서는 다음에 대해 가르칩니다. 로그 구조의 병합 트리 일명 LSM 트리 . LSM 트리는 Amazon의 DynamoDB, Cassandra 및 ScyllaDB와 같이 확장성이 뛰어난 NoSQL 분산 키-값 유형 데이터베이스의 기반이 되는 데이터 구조입니다.
LSM 트리
LSM 트리의 간단한 버전은 2가지 수준의 트리형 데이터 구조로 구성됩니다.
- Memtable이며 완전히 메모리에 상주합니다(T0이라고 가정해 보겠습니다).
- 디스크에 저장된 SStable(T1이라고 가정)
단순 LSM 트리
새로운 레코드가 memtable T0 구성 요소에 삽입됩니다. 삽입으로 인해 T0 구성 요소가 특정 크기 임계값을 초과하는 경우 항목의 연속 세그먼트가 T0에서 제거되고 디스크의 T1에 병합됩니다.
LSM 작업 흐름
LSM은 주로 읽기 및 쓰기 작업을 최적화하기 위해 3가지 개념을 사용합니다.
- 정렬된 문자열 테이블(SSTable) : 데이터는 정렬된 순서로 정렬되므로 데이터를 읽을 때마다 시간 복잡도는 최악의 경우 O(Log(N))가 됩니다. 여기서 N은 데이터베이스 테이블의 항목 수입니다.
1. SS테이블
- 멤테이블 :
- 인메모리 구조
- 데이터를 정렬된 방식으로 저장합니다.
- 후기입 캐시 역할을 합니다.
- 특정 크기에 도달하면 해당 데이터가 SSTable로 데이터베이스에 플러시됩니다.
- 마찬가지로 디스크의 SSTable 수가 증가하고 레코드에 일부 키가 없는 경우
- 해당 키를 읽는 동안 모든 SSTable을 읽어야 하므로 읽기 시간 복잡성이 증가합니다.
- 이 문제를 극복하기 위해 Bloom 필터가 등장합니다.
- 블룸 필터는 99.9%의 정확도로 레코드에 키가 누락되었는지 알려줄 수 있는 공간 효율적인 데이터 구조입니다.
- 이 필터를 사용하려면 항목이 기록될 때 항목을 추가하고 읽기 요청 시작 시 키를 확인하여 요청이 처음 들어올 때 더 효율적으로 요청을 처리할 수 있습니다.
멤테이블 표현
- 압축 :
- 디스크에 SSTable로 데이터를 저장하고 있으므로 N SSTable과 각 테이블의 크기는 중
- 그렇다면 최악의 경우 읽다 시간 복잡도는 O( N* 로그(M) )
- 따라서 SSTable의 수가 증가함에 따라 읽기 시간 복잡도 또한 증가합니다.
- 또한 데이터베이스에서 SSTable을 플러시할 때 동일한 키가 여러 SSTable에 존재합니다.
- 여기에서는 Compactor를 사용합니다.
- Compactor는 백그라운드에서 실행되어 SSTable을 병합하고 동일한 행을 여러 개 제거하고 최신 데이터가 포함된 새 키를 추가하고 이를 새로운 병합/압축된 SSTable에 저장합니다.
3.1. 디스크에 플러시된 SSTable
3.6. 압축기는 2개의 SSTable을 1개의 SSTable로 압축했습니다.
결론:
- 쓰기는 메모리 내 트리(Memtable)에 저장됩니다. 필요한 경우 모든 지원 데이터 구조(블룸 필터 및 희소 인덱스)도 업데이트됩니다.
- 이 트리가 너무 커지면 정렬된 순서로 키와 함께 디스크에 플러시됩니다.
- 읽기가 들어오면 블룸 필터를 사용하여 확인합니다. 블룸 필터가 값이 존재하지 않음을 나타내는 경우 클라이언트에 키를 찾을 수 없다고 알립니다. 블룸 필터가 값이 존재한다는 것을 의미하는 경우 SSTable을 최신 항목부터 가장 오래된 항목까지 반복하기 시작합니다.
- LSM 시간 복잡성
- 읽기 시간: O(로그(N)) 여기서 N은 디스크의 레코드 수입니다.
- 쓰기 시간: 오(1) 메모리에 기록되는 대로
- 삭제 시간: O(로그(N)) 여기서 N은 디스크의 레코드 수입니다.
- LSM 트리는 2개 이상의 필터를 사용하여 보다 효율적인 데이터 구조로 수정될 수 있습니다. 그 중 일부는 bLSM, Diff-Index LSM입니다.