자료 구조와 알고리즘
데이터베이스나 파일 시스템의 인덱스에 이진 탐색 트리가 아니라 B 트리(B+ 트리 포함)가 자주 쓰이는 주된 이유는?
- A한 노드에 많은 키를 갖게 하여 트리를 낮게 만들고, 노드를 한 번 읽을 때마다 범위를 크게 좁힐 수 있으므로, 디스크 등의 블록 읽기 횟수를 줄일 수 있기 때문
- B노드마다 키를 하나만 가지므로, 비교 횟수가 이진 탐색 트리보다 적어지기 때문
- C삽입해도 모양을 정돈할 필요가 없으므로, 구현이 이진 탐색 트리보다 간단하기 때문
정답과 해설 보기
정답: A. 한 노드에 많은 키를 갖게 하여 트리를 낮게 만들고, 노드를 한 번 읽을 때마다 범위를 크게 좁힐 수 있으므로, 디스크 등의 블록 읽기 횟수를 줄일 수 있기 때문
디스크나 SSD는 1바이트라도 수 KB의 블록 단위로 읽으므로, 읽기 횟수를 줄이는 것이 중요합니다. B 트리는 한 노드(1블록)에 수백 개의 키를 갖게 하여 노드를 한 번 읽을 때마다 수백 갈래로 분기할 수 있으므로, 예를 들어 1억 건이라도 높이 3~4단으로 목표 데이터에 도달합니다. 삽입이나 삭제로 노드가 넘치면 분할하고, 적어지면 병합하여 모든 리프의 깊이를 같게 유지합니다. 이진 탐색 트리에서는 1억 건이면 적어도 27단 정도가 되며, 단마다 다른 블록을 읽으면 느려집니다.