이진탐색트리
이진 탐색 트리는 이진탐색의 개념을 트리 형태의 구조에 접목한 자료구조로, 선형시간이 소요되는 연결 리스트 자료구조의 수행시간을 향상하기 위한 자료구조이다.
※ 이진탐색 : 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어가며 특정항목을 찾는다.
구조
단순 연결 리스트에서는 각 노드가 다음 노드만을 가리키므로 이진 탐색을 적용하기 어렵다.
반면, 이진 탐색 트리는 각 노드가 왼쪽 자식 노드와 오른쪽 자식 노드를 가지며, 데이터의 크기에 따라 노드가 배치된다.
이러한 구조를 통해 탐색 시 매 단계마다 탐색 범위를 절반으로 줄일 수 있어 효율적인 탐색이 가능하다.
이진탐색 트리 조건
각 노드 n에 저장된 키가 n의 왼쪽 서브 트리에 있는 노드에 저장된 키보다 크고, n의 오른쪽 서브트리에 있는 노드의 키보다 작아야 한다.
즉,
왼쪽 서브트리 < 현재 노드 < 오른쪽 서브트리
보완방법
이진 트리 형태의 자료구조는 대용량의 데이터 처리에 효율적이지 못하다.
이진트리가 가질 수 있는 최대 자식수는 2인데, 대용량 데이터를 처리하려면 트리의 높이가 높아지고 탐색시간이 길어지기 때문이다.
노드에 수백에서 수천개의 키를 저장하여 트리의 높이를 낮추고, 다방향 검색을 하면 이와같은 문제점을 해결할 수 있다.
B-Tree
한 노드에 여러 키와 데이터를 저장하는 균형 트리
1) 모든 노드는 동일한 깊이를 갖는다.
2) 루트가 아닌 각 노드의 자식 수는 ⌈M/2⌉ 이상 M 이하이다.
3) 루트의 자식 수는 2 이상이다.
B+Tree
모든 실제 데이터는 리프 노드에 저장되고, 내부 노드는 탐색을 위한 키만 가지는 균형 트리
1) 모든 리프 노드는 동일한 깊이를 갖는다.
2) 내부 노드는 키와 자식 포인터만을 가지며, 탐색을 위한 인덱스 역할을 수행한다.
3) 모든 데이터는 리프 노드에만 저장된다.
4) 리프 노드들은 연결 리스트 형태로 서로 연결되어 있어 순차 탐색이 용이하다.
5) 각 노드의 자식 수는 B-Tree와 동일하게 최소 ⌈M/2⌉ 이상, 최대 M 이하를 만족한다.
B-Tree vs B+Tree
| 구분 | B-Tree | B+Tree |
|---|---|---|
| 데이터 저장 위치 | 모든 노드에 분산 | 리프 노드에만 집중 |
| 내부 노드 구조 | 키 + 데이터 (무거움) | 키만 (가벼움) |
| fan-out (자식 수) | 작음 | 큼 |
| 트리 높이 | 높음 | 낮음 |
| 디스크 I/O | 많음 | 적음 |
| 리프 노드 연결 | 없음 | 있음 (순차 접근 가능) |
| 범위 검색 | 느림 | 빠름 |
내부 노드에서 데이터를 제거해 구조를 가볍게 만들면 더 많은 키를 담을 수 있어 리프노드에 담을 수 있는 자식수가 증가하고, 그 결과 트리의 높이가 낮아져 디스크 접근 횟수(I/O)가 줄어든다.
따라서 디스크 기반 대용량 데이터 환경에서는 B+Tree가 더 적합하다.
시스터디 결론
질문
수천만 건의 회원 정보가 메모리에 다 올라가지 않고 디스크에 저장돼 있습니다. 회원번호 하나 찾기도 자주 하고, 100000번~200000번 회원을 순서대로 읽기 같은 작업도 자주 합니다. 어떤 자료구조가 좋을까요?
답변
리프 노드에 데이터가 집중되고, 리프 노드 간 연결을 통해 순차 접근이 가능하므로 단건 조회와 범위 조회가 모두 중요한 디스크 기반 대용량 데이터 환경에서는 B+Tree가 가장 적합합니다.
