Index 2편 - Index 구현 (B+Tree)

인덱스는 어떻게 구현되어 있을까

이전에 인덱스는 필요한 컬럼을 미리 정렬해두어 검색속도를 빠르게 한다라는 것을 개념적으로 이해 했는데, 실제로 이런 인덱스는 어떻게 구현이 되어 있을까?

먼저 인덱스는 트리구조에 대해 알아야한다. 고건 이전 게시물에서 작성해놧슴.

 

[Algorithm] 직접 구현해 본 트리, 그리고 힙

 

B+ Tree 구조

위 게시물을 통해 완전 이진트리의 높이는 최대 O(log(N))임을 알 수 있었다.

트리 구조는 탐색마다 반씩 날려버리기 때문에 좋은 자료구조인데, 이를 더 개선한 것이 바로 Balance Tree (B-Tree) 라는 자료구조이다.

일반 트리와 다르게 B 트리는 하나의 노드가 여러개의 키를 가질 수 있는 균형 트리이다.

B 트리는 각 노드가 여러개의 키를 포함하고,오름차순으로 정렬되어 있으며 / 노드의 키 개수가 N 개라면 해당 노드는 최대 N+1개의 자식 노드를 가질 수 있다.

또한 모든 리프 노드(자식 노드가 없는 노드)는 동일한 레벨에 위치하여 트리의 균형을 유지할 수 있다.

위 그래프를 예시로 보면, 부모 노드에 55,65라는 2개(N개)의 값이 저장되어 있다면 자식 노드는 3개(N+1)를 가질 수 있다.

그 케이스는 다음과 같다 -> 55보다 작은 값 / 55 초과, 65 미만 / 65보다 큰값

이러한 특징을 통해 B 트리는 이진 트리에 비해 검색 성능과 데이터 관리의 효율이 증가되게 된다.

 

B트리 장점 정리

B트리는 높이가 낮고, 한 노드에서 여러 키를 비교하기 때문에 리프 노드까지 탐색 속도가 완전 이진 트리에 비해 빠르고 효율적이다.

특히 디스크 I/O 기반 시스템에서는 B트리가 훨씬 좋은 성능을 보여준다.

 

한번 더 개선한 B트리 : B+트리

MySql에서 사용하는 InnoDB의 기본 스토리지 엔진은 인덱스를 사용할 때 B+트리를 사용한다.

사진에서 보이듯이, 기존 b트리의 리프노드간에 간선을 추가하여 기존의 부모를 통한 범위 탐색 뿐만이 아닌, 리프노드간의 범위 탐색도 빠르게 처리할 수 있게 된다.

 

B트리 vs B+트리

무조건적으로 B+ 트리가 좋은 것이 아니다. 각자의 장단점이 있다.

B+트리는 B트리에 비해 메모리 효율성이 좋은데, 그 이유는 B트리는 각 노드에 데이터 주소 값 뿐만 아니라 실제 데이터의 value 까지 오름차순으로 정렬하여 저장한다.

반면 B+트리는 리프 노드에만 실제 데이터가 저장되기 때문에 메모리 효율이 훨씬 높다.

하지만 B+트리는 리프노드간 연결을 나타나내는 범위 데이터를 추가로 관리해야하기 때문에, 데이터 생성/수정/삭제시 B 트리보다 더 많은 오버헤드가 발생할 수 있다.

 

그러면 걍 해시테이블 쓰면 안되나요?

해시 테이블은 대표적인 O(1) 복잡도를 가진 자료구조이다.

해시테이블을 사용하지 않는 근본적인 이유는 바로 범위 검색이 안되기 때문이다.

B+트리의 최대 장점이 실제 데이터가 저장된 리프 노드들이 간선으로 연결되어 범위 검색에 유리하던 점이었는데, 해시 테이블은 해당 상황에선 좋은 성능을 보여주지 못한다.