내생각

데이터베이스 인덱스는 왜 'B-Tree'를 선택 했을까?

songjb 2025. 5. 26. 15:34

B-Tree란?

B-Tree는 기존 이진 탐색 트리에서 최악의 경우 시간 복잡도가 O(N)이 되는 문제를 해결하기 위해, 노드들이 한쪽으로 치우치지 않도록 균형을 유지하도록 설계된 트리이다.

 

그렇다면 데이터베이스 인덱스는 왜 B-tree를 선택 했을까?

 

배열을 사용하지 않는 이유

데이터베이스에 수십억건의 대량의 데이터가 저장될 수 있는데, 이를 배열로 관리하면 메모리에 모든 데이터를 한 번에 올려야 하므로 비효율적이다.

또한 삽입, 삭제시 최악의 경우 O(N)으로 비효율적이다.

 

연결 리스트를 사용하지 않는 이유

연결 리스트의 경우 배열의 단점인 삽입, 삭제시 시간복잡도가 O(1)로 효율적이다.

하지만 연결 리스트의 경우 조회시 최악의 경우 시간 복잡도가 O(N)으로 비효율적이다.

 

해시 테이블을 사용하지 않는 이유

해시 자료구조의 경우 B-Tree 계열의 시간 복잡도 O(logN)과 비교하면 조회 및 쓰기 작업의 시간 복잡도가 모두 O(1)로, 가장 빠른 자료구조이다.

하지만 데이터베이스 인덱스로 사용하기에는 무리가 있다.

이는 해시 자료구조가 정렬되어 있지 않아 범위 탐색에서 O(1)을 보장할 수 없기 때문이다.

 

물론 MySQL에서도 해시 자료구조를 전혀 사용하지 않는 것은 아니다. 단일 키 조회가 빈번하게 일어날 경우 Adaptive Hash Index라는 해시 자료구조를 사용해 조회 성능을 높일 수 있다.

 

RedBlack-Tree를 사용하지 않는 이유

Red-Black 트리는 균형 이진 탐색 트리 중 하나로, 정렬된 구조 덕분에 범위 탐색에 유리하고 시간 복잡도 또한 O(log N)로 B-Tree 계열과 같다.

그렇다면 Red-Black 트리를 사용하지 않는 이유는 무엇일까?

 

Red-Black 트리와 B-Tree 계열의 가장 큰 차이점은 하나의 노드가 가질 수 있는 데이터의 개수이다.

B-Tree는 하나의 노드가 여러 개의 데이터를 저장할 수 있고, 여러 자식 노드를 가질 수 있다.
따라서 대량의 자료를 조회할 때에도 트리의 높이가 상대적으로 낮아 디스크 I/O가 발생하는 횟수가 줄어든다.

 

Red-Black 트리는 하나의 노드에 하나의 데이터만 저장하기 때문에, 데이터가 많아질수록 트리의 높이가 높아지고 그만큼 디스크 I/O도 늘어난다.
그렇기 때문에 같은 시간 복잡도 O(log N)을 가지더라도, B-Tree 계열이 디스크 기반 저장 장치에서 더 효율적이다.

 

 

결론

 

B-Tree의 경우 하나의 노드에 여러 개의 키를 담을 수 있어 트리 높이가 낮아지고, 결과적으로 디스크 I/O 횟수가 줄어든다.
파일 시스템이 데이터를 읽고 쓰는 단위가 블록이기 때문에, B-Tree도 하나의 노드를 페이지 단위로 정렬된 데이터를 저장하여 디스크 기반 저장소에 최적화되어 있다.
조회·쓰기 작업의 최악 시간 복잡도 역시 O(log N)으로 효율적이다.

 

특히 Mysql innodb에서 사용하는B+Tree는 리프 노드에만 데이터를 저장하고, 리프 노드를 연결 리스트로 관리해 메모리를 효율적으로 활용하며 범위 탐색에도 유리하다.