[DB] 인덱스(2) - B-tree와 B+tree에 대하여

B-tree

B-tree 인덱스는 데이터를 트리 구조로 저장하는 형태의 인덱스이다.

가장 일반적이면서 중요한 인덱스 방법은 B 트리(B-tree)다. 모든 애플리케이션을 만족시킬 수 있는 최적의 메모리 구조란 사실 존재하지 않지만, 그래도 하나를 선택해야 한다면 B 트리를 선택할 것이라는 뜻이다.
출처 : Christopher J. Date <데이터베이스 시스템 6판>

 

출처 :  https://www.javatpoint.com/b-tree

B-tree 구조는 기존의 이진 검색 트리와는 다르게 각 노드에 여러 키를 가지고 있을 수 있다. 그래서 트리의 높이(depth)를 더 적게 가져갈 수 있는 이점이 있는데 이로 인해서 디스크 I/O가 줄어드므로 검색 작업이 빨라질 수 있다. 

 

그리고 각 노드에 최소한의 키가 있게 해서 균형을 유지하는데 트리의 초기 모양에 상관없이 각 작업의 시간 복잡도를 항상 O(longN)로 보장할 수 있다. 데이터 양이 증가한다고 해도 검색 속도가 갑자기 악화되지 않도록 하는 것이다.

 

더군다나 이런 트리 구조의 이점으로 데이터들이 정렬되어있을 때 이분 탐색을 통해서 시간을 줄일 수 있기 때문에 Full Scan에 비해 성능을 개선시킬 수 있다고 이야기할 수 있다.

 

 

B+tree

그런데 대부분의 데이터베이스에서는 B-tree의 수정 버전인 B+tree를 사용한다.

 

이 둘의 차이점은 무엇일까? B-tree에서는 중간 노드(Branch node/Intermediate node)들도 데이터를 가지고 있을 수 있지만 B+tree에서는 제일 밑에 위치한 리프 노드에만 데이터(정확히는 데이터의 로우 위치)를 가질 수 있게 하고 나머지 노드들은 키만 갖게 한다. 그리고 B+tree에서는 근접해있는 리프 노드들을 Linked List 형태로 연결한다.

 

그렇다면 제일 밑에 위치한 리프 노드들만 데이터를 갖게 하면서 Linked List 형태를 가지도록 변경한 이유는 무엇일까? 우리가 찾으려는 모든 데이터는 리프 노드에 있기 때문에 각각의 노드의 데이터를 살필 필요 없이 키를 통해 리프 노드를 찾아가기만 하면 된다. 그리고 리프 노드에 도착하면 순차적으로 데이터를 찾을 수 있기 때문에 여러 군데를 살필 필요가 없어 시간을 단축할 수 있는 것이다. 결론적으로 이것 또한 성능을 개선시키기 위함이다.

 

참고로 이렇게 트리 구조를 사용하는 인덱스 외에도 비트맵이나 해시를 사용하는 인덱스도 있다.

 

비트맵 인덱스는 데이터를 비트 플래그로 변환해서 저장하는 형태의 인덱스로 갱신 시 오버헤드가 크기 때문에 BI/DWH 용도, 즉 기업의 데이터 수집용으로 사용된다. 해시 인덱스는 키를 해시 분산해서 등가 검색을 고속으로 실행하고자 만들어진 인덱스인데 정렬이나 범위 검색은 할 수 없고 =, IN(), <=> 연산자들을 이용한 동일성 비교만 지원한다.

 

B+tree는 등호 뿐만 아니라 부등호(<, >, <=, >=) 모두 검색 조건에 사용할 수 있다는 것을 기억하자.

 

 

정리

• 웹 어플리케이션에서 사용하는 데이터베이스의 인덱스는 보통 B-tree 및 B+tree 구조를 사용한다.
• B-tree 및 B+tree를 사용하는 이유
  • 각 노드에 여러 키를 가지고 있어서 트리의 높이를 적게 설정할 수 있기 때문에 I/O 접근 횟수를 줄여 검색 성능을 높일 수 있다.
  • 트리 구조에서 균형을 유지하기 때문에 같은 시간 복잡도(O(logN))를 균일하게 제공할 수 있다.
• B-tree와 B+tree의 차이점
  • B-tree는 중간 노드에 데이터를 가지고 있으므로 자주 사용하는 데이터일 때 루트 노드와 가까이 배치하면 빠르게 접근할 수 있다.
  • B+tree는 리프 노드에만 데이터를 가지고 있고 Linked List 형태로 연결했기 때문에 여러 노드들의 데이터를 탐색할 필요 없이 빠르게 리프 노드에 접근해서 선형 탐색을 할 수 있다.

 

 

참고

• SQL BOOSTER
• SQL 레벨업
• B+tree
• Introduction of B-Tree
• What are the differences between B trees and B+ trees?