[MySQL] DB의 인덱스로 B+트리를 사용하는 이유

MySQL에서 B+ 트리 자료구조를 인덱스로 활용하는 이유가 무엇일까?

 

B+ 트리를 DB 인덱스로 사용하는 이유는 크게 두 가지이다.

 

시간 복잡도

 B+ 트리는 어떤 경우에도 O(log N)의 시간 복잡도를 가지기 때문에 빠른 검색이 가능하다. 이는 데이터가 크거나 데이터베이스가 복잡해져도 효율적인 조회 성능을 보장하는 중요한 장점이다.

 

 예를 들어 이진 트리의 경우 최대 O(N)의 시간 복잡도를 가지게 된다.

 

 

 

하지만 B+ 트리는 균형 트리의 일종으로, 왼쪽과 오른쪽 노드의 밸런스를 항상 유지한다.

 

 

디스크 I/O의 효율성

그럼 이런 의문이 들 수 있다.  AVL 트리, 이진 탐색 트리, 레드-블랙 트리 등의 자료구조도 균형 잡힌 트리인데, 왜 B+ 트리일까?

 

이 의문점을 해소하려면 우선 한 가지 개념을 알아야한다. 바로 관계형 DB에서의 페이지(Page) 개념이다.

 

관계형 DB의 페이지

관계형 DB에서 페이지(page)는 데이터를 물리적으로 저장하고 관리하는 기본 단위이다.

 

만약 아래와 같은 테이블이 있다고 가정해보자.

ID	Name	Age	Gender
1	John	24	Male
2	Marry	29	Female
3	Alice	43	Male

 

그리고 이런 데이터는 디스크에 저장이 된다.

 

그럼 만약 ID 1번을 조회한다면, Name과 Age, Gender에 각각 디스크 접근이 이루어져야할까? 아마도 매우 비효율적일 것이다.

 

디스크 I/O는 오버헤드가 굉장히 큰 작업이기 때문이다. 디스크의 물리적 특성 때문에 접근 속도가 느리기 때문에 성능 저하와 오버헤드가 발생한다.

 

 

 그래서 데이터를 효율적으로 읽고 쓰기 위해 데이터를 작은 단위로 처리하는 것이 아니라, 큰 블록으로 처리하여 디스크 입출력(I/O)을 최소화하게 되는데 여기서의 큰 단위가 바로 페이지이다.

 

 즉 데이터를 페이지 단위로 읽고 쓰게 된다. MySQL의 경우 InnoDB 스토리지 엔진에서 기본 페이지 크기는 16KB이다.

 

 

 이렇게 한 번에 데이터를 많이 가져오려면,  AVL 트리, 이진 탐색 트리, 레드-블랙 트리로는 부족하다. 각 노드에는 하나의 노드만 사용할 수 있기 때문이다.

 

 

 

 

B-트리와 B+트리 특징

이러한 DB의 특성을 알고나면, B- 트리와 B+ 의 트리의 가장 큰 특징이 무엇인지 알 것이다.

 

바로 균형을 자동으로 맞춰 시간복잡도를 줄이고,하나의 노드에 많은 정보를 담을 수 있기 때문에 디스크 접근에 유리하다는 것이다.

 

 

mysql의 innoDB에서는 왜 B+트리를 선택하게 되었을까? 아래에서 살펴보자.

 

 

B-트리

https://velog.io/@juhyeon1114/MySQL-Index%EC%9D%98-%EA%B5%AC%EC%A1%B0-B-Tree-BTree

 

B- 트리는 위처럼 모든 노드에 데이터 저장한다. 리프 노드뿐 아니라 중간 노드와 루트 노드에도 데이터가 저장된다.

 

 

B+ 트리

반면 B+ 트리는 B- 트리의 특성을 계승하면서도, 데이터베이스의 인덱스로 더욱 적합하도록 설계된 구조다. 

 

그 이유는 두 가지인데, 모든 데이터는 리프 노드에만 저장된다는 점, 리프 노드 간 Linked List 연결이 되어있다는 점이 있다.

 

 

모든 데이터가 리프 노드에 저장

 B+ 트리는 데이터가 모두 리프 노드에만 저장되고, 중간 노드와 루트 노드에는 데이터 대신 키만 저장된다. 이러한 구조 덕분에 전체적인 트리의 높이가 더 낮아지고, 데이터가 디스크의 특정 페이지 크기에 맞춰 효율적으로 저장된다. 

 

 하나의 데이터만 찾을 경우에 중간에서 데이터를 찾게되면 더 이상의 탐색을 중지하는 B-Tree와는 다르게 항상 리프 노드까지 접근해 언제나 O(LogN)의 시간복잡도를 가지게 된다. 모든 데이터가 선형으로 연결되어 있기 때문에 여러 개의 데이터를 순차적으로 탐색해야 하는 경우 더 빠르게 찾을 수 있다는 장점이 생긴다.

 

리프 노드 간 LinkedList 연결

B+ 트리는 리프 노드들이 Linked List로 연결되어 있어 순차 탐색과 범위 탐색에 매우 유리하다. 이 연결을 통해 특정 범위 내의 데이터를 빠르게 조회할 수 있다.

 

 

+) B+ 트리에서 리프 노드를 Linked List로 연결하는 이유

 리프 노드의 데이터가 순차 탐색을 위해 연결되어야 한다면, Array로 연결할 수도 있겠지만 B+ 트리는 Linked List로 연결된다. 그 이유는 Array에 데이터를 저장하면 검색은 빠르지만, 중간에 데이터를 삽입하거나 삭제할 때는 비효율적이기 때문이다.

 예를 들어 중간에 데이터를 삽입할 경우, 이후 데이터들을 한 칸씩 shift해야 하므로 최악의 경우 O(N)의 시간 복잡도를 가지게 된다. 반면, Linked List 구조에서는 이러한 삽입 및 삭제가 상대적으로 효율적이다.

 따라서 B+ 트리는 Linked List를 활용해 리프 노드 간 연결을 최적화했다.