SQL 데이터베이스의 균형 검색 트리(B-Tree)

B-트리(B-Tree) 검색 트리가 인덱스를 빠르게 만든다

인덱스의 리프(leaf) 노드는 임의의 순서로 저장됩니다. 즉, 디스크상의 물리적 위치는 인덱스 정렬 순서에 따른 논리적 위치와 일치하지 않습니다. 이는 페이지가 뒤섞인 전화번호부와 같습니다. “Smith”를 찾는데 “Robinson”에서 먼저 펼쳤다고 해서 Smith가 Robinson 바로 뒤에 나온다는 보장은 전혀 없습니다. 데이터베이스는 뒤섞인 페이지들 사이에서 원하는 항목을 빠르게 찾기 위해 두 번째 구조가 필요합니다. 그것이 바로 균형 검색 트리—줄여서 B-트리입니다.

그림 1.2 B-트리 구조

그림 1.2는 30개 엔트리를 가진 예시 인덱스를 보여줍니다. 이중 연결 리스트(doubly linked list)가 리프 노드들 사이의 논리적 순서를 확립합니다. 루트(root) 노드와 브랜치(branch) 노드는 리프 노드들 사이를 빠르게 검색할 수 있도록 지원합니다.

그림은 한 브랜치 노드와, 그 노드가 참조하는 리프 노드들을 강조 표시합니다. 각 브랜치 노드 엔트리는 해당 리프 노드에 있는 가장 큰 값에 대응합니다. 첫 번째 리프 노드를 예로 들어 봅시다. 이 노드에서 가장 큰 값은 46이며, 따라서 대응되는 브랜치 노드 엔트리에 46이 저장됩니다. 다른 리프 노드도 마찬가지여서, 결국 브랜치 노드는 46, 53, 57, 83 값을 갖게 됩니다. 이 방식에 따라 모든 리프 노드가 브랜치 노드에 의해 커버될 때까지 브랜치 계층이 구축됩니다.

이 페이지가 마음에 드신다면, 다음도 관심 있을 수 있습니다 …

… 메일링 리스트 구독, 무료 스티커 받기, 책 구매, 또는 트레이닝 참여.

그 다음 계층도 유사하게 만들어지되, 첫 번째 브랜치 노드 레벨 위에 구축됩니다. 이 절차는 모든 키가 단 하나의 노드, 즉 _루트 노드_에 들어갈 때까지 반복됩니다. 이 구조를 _균형 검색 트리_라고 부르는 이유는, 트리의 깊이가 모든 위치에서 동일하기 때문입니다. 즉, 루트 노드에서 리프 노드까지의 거리가 어디서나 같습니다.

참고

B-트리는 균형 트리(balanced tree)이지, 이진 트리(binary tree)가 아닙니다.

인덱스가 한 번 생성되면, 데이터베이스는 인덱스를 자동으로 유지 관리합니다. 모든 insert, delete, update를 인덱스에도 적용하고 트리의 균형을 유지합니다. 따라서 쓰기 작업에는 유지보수 오버헤드가 발생합니다. 이에 대한 자세한 내용은 8장 “데이터 변경(Modifying Data)”에서 설명합니다.

그림 1.3 B-트리 탐색

그림 1.3은 키 “57”을 찾는 검색을 설명하기 위해 인덱스의 일부를 보여줍니다. 트리 탐색은 왼쪽의 루트 노드에서 시작합니다. 각 엔트리는 오름차순으로 처리되며, 값이 검색어(57)보다 크거나 같은(>=) 항목이 나올 때까지 진행합니다. 그림에서는 83 엔트리가 해당합니다. 데이터베이스는 대응되는 브랜치 노드로의 참조를 따라가고, 리프 노드에 도달할 때까지 같은 절차를 반복합니다.

중요

B-트리는 데이터베이스가 리프 노드를 빠르게 찾을 수 있게 해줍니다.

트리 탐색은 매우 효율적인 연산입니다—너무 효율적이어서 저는 이를 _인덱싱의 1차 능력(first power of indexing)_이라고 부릅니다. 아주 큰 데이터셋에서도 거의 즉시 동작합니다. 이는 주로 트리의 균형 덕분인데, 균형이 잡혀 있으면 모든 요소에 동일한 단계 수로 접근할 수 있기 때문입니다. 두 번째 이유는 트리 깊이의 로그(logarithmic) 증가입니다. 즉, 리프 노드 수에 비해 트리 깊이는 매우 느리게 증가합니다. 수백만 레코드를 가진 현실 세계의 인덱스는 트리 깊이가 4~5인 경우가 많습니다. 깊이 6은 거의 보이지 않습니다. “로그 스케일 확장성(Logarithmic Scalability)” 박스에서 더 자세히 설명합니다.

로그 스케일 확장성

수학에서 어떤 밑(base)에 대한 수의 로그는, 그 밑을 몇 제곱(지수, exponent)해야 그 수가 되는지를 나타냅니다 [위키백과].

검색 트리에서 밑은 브랜치 노드당 엔트리 수에 해당하고, 지수는 트리 깊이에 해당합니다. 그림 1.2의 예시 인덱스는 노드당 최대 4개 엔트리를 담을 수 있고 트리 깊이는 3입니다. 따라서 인덱스는 최대 64(4^3)개 엔트리를 담을 수 있습니다. 레벨이 하나 늘어나면 최대 256개(4^4)를 담을 수 있습니다. 레벨이 _추가_될 때마다 인덱스 엔트리의 최대 개수는 _4배_가 됩니다. 로그는 이 함수를 역으로 뒤집습니다. 그러므로 트리 깊이는 log₄(인덱스-엔트리-수)입니다.

트리 깊이	인덱스 엔트리 수
3	64
4	256
5	1,024
6	4,096
7	16,384
8	65,536
9	262,144
10	1,048,576

로그 성장 덕분에, 예시 인덱스는 트리 레벨 10개로 100만 레코드를 검색할 수 있습니다. 하지만 현실의 인덱스는 이보다 더 효율적입니다. 트리 깊이, 따라서 조회 성능에 영향을 주는 가장 큰 요인은 각 트리 노드에 들어가는 엔트리 수입니다. 이 수는—수학적으로 말해—로그의 밑에 해당합니다. 밑이 클수록 트리는 더 얕아지고, 탐색은 더 빨라집니다.

데이터베이스는 이 개념을 최대한 활용하여 각 노드에 가능한 한 많은 엔트리를 담습니다—종종 수백 개에 이르기도 합니다. 즉, 새로운 인덱스 레벨이 추가될 때마다 수백 배 더 많은 엔트리를 지원할 수 있습니다.

링크

B+트리 시뮬레이터

이전 페이지 다음 페이지

하루 만에 모든 것을 배울 수는 없습니다. 이메일, Bluesky 또는 **RSS**로 뉴스레터를 구독하고 차근차근 따라오세요. modern-⁠sql.com도 함께 살펴보시기 바랍니다.

저자 소개

이미지 2: Markus Winand 사진 Markus Winand는 modern-sql.com에서 SQL에 대한 인사이트를 제공하고, 서로 다른 시스템이 SQL을 어떻게 지원하는지 보여줍니다. 그는 과거 use-the-index-luke.com을 만들었으며, 해당 사이트는 지금도 활발히 유지보수되고 있습니다. Markus는 winand.at를 통해 트레이너, 강연자, 컨설턴트로 섭외할 수 있습니다.