Btree

• B-Tree: 다방향 탐색 트리. 대용량의 파일을 효율적으로 검색하고 갱신하기 위해 고안된 트리 형태의 자료 구조이다.
• B+Tree: B-Tree와 유사하나 실제 데이터는 최하위에 존재하며 순차적으로 연결되어 있다. 따라서 순차적인 값을 찾을때는 훨씬 유리하나 특정 값을 찾을때는 최밑단까지 가야 하는 단점이있음.
• B*Tree: B+Tree에서 합병의 비용을 줄이기 위해 재배치를 활용하도록 한 트리라고 한다.

Libraries

• stx-btree: STX B+Tree C++ Template Classes.
• cpp-btree: C++ B-tree.

Favorite site

• Source code for a balanced tree (B-tree) ¹
• btree source (by. Thomas H. Cormen) v1.0 ²³
• B-트리와 데이터베이스 인덱스 | GeekNews
  • [원본] B-trees and database indexes - 인터랙티브한 GUI 로 B-Tree 가 어떻게 작동하는지 보여준다.
• B-Trees: 예상보다 더 많은 정보를 담고 있는 데이터 구조 | GeekNews
  • [원본] B-Trees: More Than I Thought I'd Want to Know | Ben Congdon
  • 최근에 Alex Petrov의 Database Internals를 읽으면서 DBMS 스토리지 엔진 구현 방식, 특히 B-Tree 자료구조 최적화와 관련된 내용을 접함
  • 대학에서 B-Tree를 배울 때는 단순히 “더 나은 BST”라는 식으로 이해해서, 실제로 왜 쓰이는지 와닿지 않았음
  • 디스크 I/O를 고려해 대규모 데이터를 저장하고 빠르게 검색하기 위해 B-Tree 구조가 적합함
  • 이 글은 B-Tree가 왜 필요한지, 어떤 식으로 동작하는지, 그리고 실제 구현에서 어떤 최적화가 가능한지를 소개함
  • 키를 한 노드에 많이 모아 디스크 접근 횟수를 줄이는 방식 등이 주요 특징임

References