로그 구조화 병합 트리
Log-structured merge-tree |
| 로그 구조화 병합 트리 | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 유형 | 하이브리드(두 개의 트리 같은 구성 요소) | ||||||||||||||||
| 발명된 | 1996 | ||||||||||||||||
| 발명된 사람 | 패트릭 오닐, 에드워드 쳉, 디터 가울릭, 엘리자베스 오닐 | ||||||||||||||||
| 큰 O 표기법에서의 시간 복잡성 | |||||||||||||||||
| |||||||||||||||||
컴퓨터 공학에서 로그 구조화된 병합 트리(LSM 트리 또는 LSMT라고도[1] 함)는 트랜잭션 로그 데이터와 같이 삽입 볼륨이 높은 파일에 대한 인덱스 액세스를 제공하는 것이 매력적인 성능 특성을 가진 데이터 구조다.LSM 트리는 다른 검색 트리와 마찬가지로 키-값 쌍을 유지한다.LSM 트리는 둘 이상의 개별 구조물에 데이터를 유지하며, 각 구조물은 각각의 기본 저장 매체에 최적화되어 있으며, 데이터는 두 구조물 간에 일괄적으로 효율적으로 동기화된다.
LSM 트리의 한 가지 간단한 버전은 2-레벨 LSM 트리다.[2]패트릭 오닐이 설명한 대로, 2단계의 LSM 트리는 C와0 C라고1 불리는 두 개의 나무와 같은 구조로 구성되어 있다.C는0 더 작고 기억 속에 완전히 상주하는 반면, C는1 디스크에 상주한다.메모리0 레지던트 C 컴포넌트에 새 레코드가 삽입된다.삽입으로 인해0 C 구성요소가 특정 크기 임계값을 초과하는 경우, 항목의 연속적인 세그먼트가 C에서0 제거되고 디스크의 C로1 병합된다.LSM 트리의 성능 특성은 각 구성 요소가 기본 저장 매체의 특성에 맞춰 조정되고, 데이터가 병합 정렬을 연상시키는 알고리즘을 사용하여 미디어 간에 효율적으로 마이그레이션된다는 사실에서 기인한다.
실제로 사용되는 대부분의 LSM 나무는 여러 가지 수준을 사용한다.레벨 0은 메인 메모리에 저장되며 트리를 사용하여 나타낼 수 있다.온 디스크 데이터는 정렬된 데이터 실행으로 구성된다.각 실행에는 인덱스 키별로 정렬된 데이터가 들어 있다.실행은 디스크에서 단일 파일로 나타낼 수도 있고, 또는 또는 오버랩되지 않는 키 범위를 가진 파일의 모음으로 나타낼 수도 있다.특정 키에 대한 조회를 수행하여 관련 값을 얻으려면 레벨 0 트리에서 검색하고 각 실행도 검색해야 한다.
특정 키가 여러 실행에서 나타날 수 있으며, 쿼리에 대한 의미는 애플리케이션에 따라 달라진다.일부 애플리케이션은 단순히 주어진 키를 가진 최신 키-값 쌍을 원한다.어떤 애플리케이션은 적절한 집계 값을 반환하기 위해 어떤 방법으로 값을 결합해야 한다.예를 들어 Apache Cassandra에서 각 값은 데이터베이스의 행을 나타내며 행의 다른 버전은 서로 다른 열 집합을 가질 수 있다.[3]
쿼리 비용을 낮추기 위해서는 시스템이 실행 횟수가 너무 많은 상황을 피해야 한다.
bLSM과[4] Diff-Index와 같이 B+ 트리 구조를 통합하기 위한 '레벨링된' 방법에 대한 확장이 제안되었다.[5]
LSM 트리는 Apache AsterixDB, Bigtable, HBase, LevelDB, SQLite4,[6] Tarantool,[7] RocksDB, WiredTiger,[8] Apache Cassandra, IncremitDB[9], 실라DB 등의 데이터 저장소에서 사용된다.
참조
- ^ Zhang, Weitao; Xu, Yinlong; Li, Yongkun; Li, Dinglong (December 2016). "Improving Write Performance of LSMT-Based Key-Value Store". 2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS): 553–560. doi:10.1109/ICPADS.2016.0079.
- ^ 오닐 1996 페이지 4
- ^ "Leveled Compaction in Apache Cassandra : DataStax". February 13, 2014. Archived from the original on February 13, 2014.
- ^ "Archived copy" (PDF). www.eecs.harvard.edu. Archived from the original (PDF) on 27 January 2016. Retrieved 12 January 2022.
{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크) - ^ http://researcher.ibm.com/researcher/files/us-wtan/DiffIndex-EDBT14-CR.pdf
- ^ "SQLite4 with LSM Wiki". SQLite.
- ^ "An application server together with a database manager". Retrieved April 3, 2018.
Tarantool’s disk-based storage engine is a fusion of ideas from modern filesystems, log-structured merge trees and classical B-trees.
- ^ "GitHub - wiredtiger/wiredtiger: WiredTiger's source tree". December 4, 2019 – via GitHub.
- ^ Dix, Paul (October 7, 2015). "[New] InfluxDB Storage Engine Time Structured Merge Tree".
- 일반
- O'Neil, Patrick E.; Cheng, Edward; Gawlick, Dieter; O'Neil, Elizabeth (June 1996). "The log-structured merge-tree (LSM-tree)". Acta Informatica. 33 (4): 351–385. CiteSeerX 10.1.1.44.2782. doi:10.1007/s002360050048.
- Li, Yinan; He, Bingsheng; Luo, Qiong; Yi, Ke (2009). "Tree Indexing on Flash Disks". 2009 IEEE 25th International Conference on Data Engineering. pp. 1303–6. CiteSeerX 10.1.1.144.6961. doi:10.1109/ICDE.2009.226. ISBN 978-1-4244-3422-0.
- Luo, Chen; Carey, Michael J. (July 2019). "LSM-based storage techniques: a survey". The VLDB Journal. arXiv:1812.07527. doi:10.1007/s00778-019-00555-y.
