DB 인덱스의 B+Tree 자료구조
서론
저번 글(B-Tree 자료구조)에서 B-Tree에 관한 내용을 정리했다.
이번에는 B-Tree를 변형해서 DB의 인덱스 자료구조로 실질적으로 쓰이는 B+Tree에 관해 알아보겠다.
B+Tree 특징
B+Tree는 B-Tree의 핵심적인여특성(셀프 균형, 트리 구조 등)을 그대로 계승하면서, 데이터베이스나 파일 시스템에서 범위 검색과 풀 스캔을 더 효율적으로 처리하기 위해 구조를 최적화한 모델이라고 보면된다.
이전 B-Tree 글에서도 소개했지만, B+Tree 시뮬레이션까지 지원하니 꼭 직접 조작하며 흐름을 파악해 보시길 추천드린다.
B-Tree VS B+Tree
위에서 기술한 것처럼 B+Tree는 결국 B-Tree에서 변형된 것이기 때문에, 어떤 특징이 추가되었는지 위주로 생각하면 이해가 빠르다. B-Tree와 B+Tree의 주요 차이점은 다음과 같다.
[데이터 저장 방식 차이]
B-Tree는 모든 노드(루트, 내부, 리프)가 key와 실제 데이터(Value/Pointer)를 함께 가질 수 있다. 운 좋게 루트 노드에서 데이터를 찾으면 검색이 매우 빨리 끝날 수 있는 것.
B+Tree는 실제 데이터는 오직 리프 노드에만 저장된다. 중간 노드들은 데이터를 찾아가기 위한 가이드(인덱스) 역할만 수행하며 key 값만 복사해서 가지고 있다.
B-Tree와 다르게 B+Tree는 내부 노드에 실제 데이터가 없기에 탐색 시 다음과 같은 규칙을 가진다.
부모 노드에 Key 값이 10, 20이 있다면 자식 노드는 ? < 10 | 10 <= ? < 20 | 20 <= ? 의 범위를 가지게 된다.
이는 B-Tree의 경우 ? < 10 | 10 < ? < 20 | 20 < ?의 범위를 가지는 것과 대조된다.
모든 실제 데이터는 리프 노드에 있기 때문에, 검색 시 반드시 리프 노드까지 내려가야 한다는 점이 큰 차이다.
[리프 노드 간 연결]
B-Tree는 리프 노드들이 서로 연결되어 있지 않다. 특정 범위의 데이터를 찾으려면 트리 위아래를 반복해서 왔다 갔다 해야한다.
B+Tree는 모든 리프 노드가 연결 리스트 형태로 이어져 있다. 덕분에 한 번 리프 노드에 도달하면, 그다음 데이터는 트리를 다시 타지 않고 옆으로 쭉 읽기만 하면 된다.
[캐시 효율성(Disk I/O)]
B+Tree는 중간 노드에 데이터를 담지 않기 때문에, 하나의 메모리 페이지에 더 많은 Key를 담을 수 있다. 이는 트리의 높이를 낮추고 디스크 I/O 횟수를 줄이는 효과를 가져온다.
[기억] 주말에 그림자료 만들어 추가해서 확실히 이해하도록 할 것