T-tree 인덱스: 메인 메모리 DB를 위한 균형 트리 설계
T-tree의 노드 배열, GLB/LUB 근접 탐색, AVL 균형 유지 방식과 메인 메모리 인덱스 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
노드 안에 여러 키를 담는 균형 인덱스
T-tree는 AVL-Tree의 이진탐색 특성과 B-Tree의 저장·업데이트 효율을 결합한 메인 메모리 데이터베이스(Main-Memory DB, MMDB) 지향 인덱스 구조다. 상위 구조는 AVL 계열의 균형 이진탐색트리로 유지하되, 각 노드는 하나의 키 대신 정렬된 키 집합을 보관한다.
이 방식은 노드당 키 배열로 저장 밀도를 높이고 회전 빈도를 낮추는 데 목적이 있다. GLB/LUB를 이용한 근접값 탐색도 가능하므로, 실시간 OLTP처럼 삽입·삭제 지연이 짧아야 하면서 로그급 탐색 시간이 필요한 환경을 대상으로 한다.
노드는 보유하는 자식에 따라 다음처럼 구분된다.
- 내부노드는 좌·우 서브트리를 모두 가지며, 최대 수용량
m은 T-tree 생성 시 결정된다. - 하프리프노드는 한쪽 서브트리만 가지며 자식 포인터도 1개다.
- 리프노드는 자식과 포인터가 없다.
키 범위로 이동하고 노드 안에서 찾는다
각 노드는 최대 m개의 정렬된 키 배열과 min/max, 키 개수, 높이 메타데이터, 좌·우·부모 포인터를 가진다. 키 배열이 메모리에서 연속적으로 배치되므로 캐시 지역성을 확보할 수 있다.
노드 수용량 m을 사용하면 트리 높이는 log2(N/m) 수준으로 낮아진다. AVL 트리보다 노드 수와 회전 빈도가 줄어드는 이유다.
탐색은 현재 노드 A의 키 범위를 기준으로 갈린다.
k < min(A)이면 좌측 서브트리로 이동한다.k > max(A)이면 우측 서브트리로 이동한다.- 그 외에는 노드 A의 배열 안에서 이진검색한다. 이 내부 탐색 비용은
O(log m)이다.
정확한 키가 없더라도 인접값이 필요할 수 있다. GLB(A)는 min(A)보다 작은 값 가운데 가장 큰 값이며, 좌측 서브트리에서 min(A)에 가장 가까운 최대값을 고른다. LUB(A)는 max(A)보다 큰 값 가운데 가장 작은 값으로, 우측 서브트리에서 max(A)에 가장 가까운 최소값을 선택한다. 범위 스캔에서는 이 경계와 서브트리 순회를 함께 사용한다.
null 자식에 도달하면 검색은 실패한다. 중복 키를 허용해야 한다면 노드 내부 다중 삽입이나 카운팅 전략이 필요하다.
삽입과 삭제 뒤에 균형을 되찾는 방식
삽입은 위치를 찾고, 대상 노드에 여유 공간이 있는지 확인한 뒤, 삽입 또는 분산을 수행하고 균형을 검증하는 순서로 진행된다. 여유 공간이 있으면 배열의 정렬 위치에 새 키를 넣는다.
노드가 가득 차면 최소값을 제거해 공간을 만든 다음 새 키를 삽입한다. 제거한 최소값은 좌측 서브트리에 다시 삽입한다. 이후 높이를 갱신하고 LL/LR/RR/RL 회전을 적용한다.
삭제는 대상 키를 찾은 뒤 삭제하고, 언더플로우 검사와 대체·병합을 거쳐 균형을 회복한다. 내부노드에서 키를 제거한 경우 좌측 서브트리의 최대값인 전임자로 대체한다. 키 수가 ⌊m/2⌋ 미만인 언더플로우가 생기면 인접 노드에서 재분배하거나 병합하고, 이어서 AVL 규칙에 따라 재균형한다.
노드 내부에 여러 키가 있으므로 높이 변화가 완화된다. 삽입과 삭제 때 필요한 전체 회전 횟수도 줄어들어 업데이트 지연을 낮출 수 있다.
메모리 중심 워크로드에서의 선택지
T-tree는 포인트 룩업 비중이 높은 메인 메모리 OLTP 인덱스에 맞는다. 빈번한 삽입·삭제에서도 재균형 비용을 짧게 유지하려는 경우에 사용할 수 있다.
키-값 세션 스토어의 인메모리 인덱스처럼 수명이 짧은 데이터를 빠르게 수선해야 하는 환경도 대상이다. 시계열·IoT 스트림에서는 최근 구간에 삽입이 집중될 때, 최근 타임스탬프 근접 조회처럼 GLB/LUB 기반 보정이 필요한 경우를 생각할 수 있다. 같은 N에서 AVL보다 노드 수를 줄일 수 있으므로, 메모리가 제한된 환경에서 메타데이터와 포인터 오버헤드를 낮추는 대안이 되기도 한다.
최신 인메모리 엔진은 ART, Bw-Tree, Masstree 등을 사용하는 경향도 있다. 워크로드와 하드웨어에 따른 최신 정보 확인이 필요하다.
높이와 캐시 지역성이 만드는 차이
트리 높이는 log2(N) − log2(m)으로 줄어든다. 예를 들어 N=10^7, m=16이면 23.25 − 4 ≈ 19.25 레벨로, 약 17% 감소한다.
노드 내부의 연속 배열 접근은 L1/L2 적중률 향상에 기여한다. 내부 탐색은 O(log m)이며, m이 작을수록 상수항은 감소한다. 삽입과 삭제에서는 회전 빈도가 낮아지고 분할·병합은 드물며 지역적으로 일어난다. GLB/LUB는 근접 검색과 범위 질의의 응답시간을 안정화하는 데 쓰인다.
공간 측면에서는 노드당 다중 키를 저장하므로 AVL 대비 효율이 개선된다. 반면 B/B+tree와 비교하면 페이지·브랜치 효율은 열위일 수 있고 포인터 오버헤드는 남는다. 구현 복잡도는 AVL보다 높고 B+tree보다 낮거나 유사하다.
| 지표 | AVL-Tree | T-tree | B+Tree |
|---|---|---|---|
| 점검색 성능 | O(log N), 높이 큼 | O(log N), 높이 감소·노드 내부 O(log m) | O(log_b N), 디스크/페이지 효율적 |
| 범위검색 | 중간 | min/max·GLB/LUB로 양호 | 매우 우수(리프 체인) |
| 공간 효율 | 낮음(노드 1키 중심) | 중간(다중 키 저장, 포인터 오버헤드 존재) | 높음(페이지 단위 밀집 저장) |
| 캐시/페이지 친화성 | 낮음 | 중간~양호(연속 배열) | 높음(대용량 페이지 최적화) |
| 삽입/삭제 비용 | 회전 빈도 높음 | 회전 빈도 낮음, 국소 재분산 | 분할/병합 비용 존재, 배치 삽입 유리 |
| 동시성/락 | 미세락 용이 | 미세락 가능, 노드 내부 경합 고려 | 페이지락/래치 최적화 성숙 |
| 구현 난이도 | 낮음~중간 | 중간(내부 배열·재분산 로직) | 중간~높음(페이지/버퍼/분할 알고리즘) |
운영 설계에서 확인할 제약
T-tree는 O(log N) 탐색, 짧은 삽입·삭제 지연, AVL 대비 저장 효율 향상, 캐시 지역성 개선을 제공한다. 다만 B/B+tree보다 저장공간과 페이지 활용도가 열위일 수 있고, 노드 내부 재분산과 언더플로우 처리는 복잡하다. N이 매우 커지면 높이 한계도 고려해야 한다.
m은 CPU 캐시라인에 맞춘다. 예를 들어 64B 기준으로 키와 포인터 크기를 고려하며, 언더플로우 임계치는 ⌊m/2⌋ 전후를 권장한다.
동시성 제어에서는 노드 수준 래치와 내부 배열 업데이트 시 단기 스핀락을 사용한다. 회전과 병합은 상위에서 하위로 잠그는 순서를 유지해 데드락을 피한다. 메모리는 고정 크기 노드 풀과 재사용 큐를 활용하고 NUMA 로컬리티를 유지한다. 장애 내성을 위해서는 WAL 또는 스냅샷을 병행하며, 리플레이 시 삽입 순서가 변하지 않도록 보장한다.
페이지 기반 스토리지나 대규모 범위 스캔이 중심이라면 B+tree 계열을, 최신 인메모리 환경이라면 ART나 Masstree 같은 대안을 검토할 수 있다. T-tree는 MMDB, 세션 인덱스, 근접 탐색 중심 시나리오에서 우선 고려할 만하다.