🟣 왜 트리인가: 순차 파일이 못 하던 것
앞 장에서 순차 파일은 정렬 덕에 이진 탐색은 되지만 중간 삽입이 뒤 레코드를 전부 밀어내는 게 문제였다. 정렬 상태를 유지하면서 삽입도 값싸게 하려면, 데이터를 물리적으로 나란히 두지 말고 포인터로 이어 논리적인 순서만 지키면 된다. 배열 대신 연결 구조를 쓰자는 것인데, 여기에 이진 탐색의 규칙을 얹은 것이 이진 탐색 트리(BST)다.
BST의 규칙은 한 줄이다. 어떤 노드를 기준으로 왼쪽 하위 트리의 모든 키는 그 노드보다 작고, 오른쪽 하위 트리의 모든 키는 크다. 이 규칙 덕에 루트에서 시작해 키를 비교하며 왼쪽이나 오른쪽으로 내려가면 탐색이 된다. 한 번 비교할 때마다 남은 후보가 절반으로 줄어드는, 이진 탐색을 트리로 옮긴 구조다.
삽입도 같은 경로를 따라간다. 새 키가 들어갈 자리를 탐색하듯 내려가 빈 자리에 매단다. 순차 파일처럼 뒤를 밀 필요가 없다. 트리의 높이가 h면 탐색과 삽입 모두 그 경로 길이만큼, 즉 h번의 비교로 끝난다. 균형이 잘 잡힌 트리라면 h는 대략 log₂(n)이다.
🟣 BST의 함정: 편향되면 리스트가 된다
문제는 "균형이 잘 잡힌"이라는 전제에 있다. BST의 모양은 데이터가 들어온 순서에 좌우된다. 하필 이미 정렬된 데이터를 순서대로 삽입하면, 새 키가 항상 직전 키보다 커서 계속 오른쪽으로만 매달린다. 결과는 한쪽으로 늘어진 사슬이다.
이렇게 편향된 트리는 사실상 연결 리스트다. 높이가 n에 가까워지고, 탐색은 다시 O(n)으로 떨어진다. 애써 트리를 썼는데 순차 탐색으로 되돌아간 셈이다. 게다가 정렬된 입력은 특이한 상황이 아니라 흔한 상황이다. 로그를 시간순으로 적재하거나 자동 증가하는 식별자를 순서대로 넣으면 바로 이 꼴이 된다.
그래서 BST를 실무 인덱스로 쓰려면 어떤 순서로 데이터가 들어와도 높이가 log₂(n) 근처로 유지되도록 강제해야 한다. 삽입할 때마다 트리가 한쪽으로 기울지 않게 스스로 모양을 고치는 트리, 이것이 균형 이진 탐색 트리이고 그 대표가 AVL 트리다.
🟣 AVL: 균형을 수치로 감시한다
AVL 트리는 균형을 눈대중이 아니라 숫자로 관리한다. 각 노드마다 균형 인수(balance factor)를 두는데, 이는 왼쪽 하위 트리의 높이에서 오른쪽 하위 트리의 높이를 뺀 값이다. AVL의 불변식은 모든 노드에서 이 값의 절댓값이 1 이하로 유지되는 것이다. 즉 어떤 노드도 양쪽 높이가 2 이상 벌어지지 않는다.
삽입이나 삭제로 이 불변식이 깨지면, 깨진 지점에서 회전(rotation)으로 모양을 바로잡는다. 회전은 부모와 자식의 자리를 바꿔 한쪽으로 쏠린 무게를 반대로 옮기는 국소적인 연산이다. 깨진 형태에 따라 네 가지 경우로 나뉜다. 왼쪽-왼쪽(LL), 오른쪽-오른쪽(RR)은 한 번의 회전으로 풀리고, 왼쪽-오른쪽(LR), 오른쪽-왼쪽(RL)은 두 번의 회전이 필요하다.
가장 단순한 LL 경우를 보자. 왼쪽으로만 세 노드가 이어져 균형이 깨진 상태를, 가운데 노드를 위로 끌어올리는 오른쪽 회전 한 번으로 바로잡는다.
회전은 국소적이라 값이 싸다. 삽입 경로를 타고 루트 쪽으로 올라오며 균형이 깨진 첫 노드에서 회전 한두 번이면 끝난다. 그래서 AVL은 삽입·삭제·탐색이 모두 최악에도 O(log n)을 보장한다. 앞의 편향된 BST가 정렬 입력에 무너지던 것과 대조적이다. 균형을 숫자로 감시하고 깨지는 즉시 국소적으로 고친다는 이 발상이, 뒤에 나올 B트리에서도 형태만 바뀐 채 반복된다.
🟣 그런데 디스크로 가면 AVL도 부족하다
AVL은 메모리 안에서는 훌륭하다. 문제는 이 책의 무대가 디스크라는 데 있다. 인덱스가 커서 메모리에 다 못 올리면 트리 노드도 디스크에 놓인다. 그러면 노드를 하나 따라갈 때마다 디스크 접근이 한 번 일어난다. 앞 장에서 봤듯 디스크 접근은 비싸다. 결국 탐색 비용은 트리의 높이에 정비례한다.
여기서 AVL의 한계가 드러난다. AVL은 이진 트리라 노드마다 자식이 둘뿐이고, 높이가 log₂(n)이다. n이 백만이면 높이가 대략 20이다. 키 하나를 찾자고 디스크에 스무 번 접근한다는 뜻이다. 균형은 완벽한데도 디스크 기준으로는 여전히 손이 많이 간다.
문제의 뿌리는 분기수가 2뿐이라는 데 있다. 한 노드에서 갈래가 둘밖에 없으니 트리가 깊어질 수밖에 없다. 만약 한 노드에서 수백 갈래로 뻗을 수 있다면 같은 데이터라도 높이가 훨씬 낮아진다. 디스크 접근 횟수는 높이가 결정하므로, 분기수를 키워 높이를 낮추자는 것이 다음 장의 핵심이다. 마침 앞 장에서 본 블록이 그 답을 준다. 노드 하나를 블록 하나에 채우면 노드 안에 키를 수백 개까지 담을 수 있고, 그만큼 갈래가 많아진다.
🟣 정리
- 이진 탐색 트리는 왼쪽은 작고 오른쪽은 크다는 규칙으로 탐색과 삽입을 모두 높이만큼의 비교로 처리한다. 순차 파일의 삽입 비용 문제를 푼다.
- BST의 모양은 입력 순서에 좌우된다. 정렬된 데이터를 넣으면 한쪽으로 편향돼 연결 리스트가 되고 탐색이 O(n)으로 떨어진다.
- AVL 트리는 균형 인수로 양쪽 높이차를 1 이하로 감시하고, 깨지면 회전으로 국소적으로 바로잡아 최악에도 O(log n)을 보장한다.
- 회전은 LL·RR·LR·RL 네 경우로 나뉘고, 국소 연산이라 값이 싸다.
- 디스크에서는 노드마다 접근이 한 번씩 들어 높이가 곧 접근 횟수다. 이진 트리는 분기수가 2뿐이라 높이가 log₂(n)으로 여전히 높다.
면접에서 "왜 데이터베이스 인덱스가 AVL이나 레드블랙 트리가 아니라 B트리 계열이냐"는 질문이 나오면, 답의 출발점이 바로 이 마지막 문단이다. 메모리용 균형 트리와 디스크용 인덱스는 최적화 대상이 다르다. 메모리에서는 비교 횟수를, 디스크에서는 블록 접근 횟수를 줄여야 한다.
다음 장에서는 분기수를 블록 크기만큼 키워 높이를 확 낮춘 B트리, 그리고 범위 검색까지 노린 B+트리를 본다. 데이터베이스가 실제로 쓰는 인덱스가 여기서 나온다.