T-Tree 인메모리 인덱스의 구조와 선택 기준
T-Tree의 노드 구성, AVL 유사 균형 유지, 캐시 지역성, 동시성 제어와 인메모리 인덱스 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
메모리 상주형 데이터베이스에서 인덱스는 비교 연산보다 포인터를 따라가며 발생하는 메모리 접근 비용에 더 민감할 수 있다. T-Tree는 이진 탐색 트리의 균형 특성과 B-트리 계열의 다중 키 저장 방식을 결합해, 인메모리 환경의 캐시 효율과 메모리 사용성을 겨냥한 구조다.
노드 배열을 가진 균형 이진 탐색 트리
T-Tree는 이진 탐색 트리 형태를 따르되, 각 노드가 정렬된 키 배열을 보관한다. 균형은 AVL 트리와 유사한 LL/LR/RL/RR 회전 규칙으로 관리한다.
구조가 지켜야 할 불변식은 다음과 같다.
- 노드 안의 키는 정렬 상태를 유지한다.
- 왼쪽 서브트리의 모든 키는 노드 최소 키보다 작고, 오른쪽 서브트리의 모든 키는 노드 최대 키보다 크다.
- 노드 점유도는 최소·최대 용량 범위를 벗어나지 않도록 언더플로와 오버플로 처리 규칙을 둔다.
노드 내부에서는 이진 탐색으로 키를 찾고, 노드 간 이동은 최소·최대 키와의 비교로 결정한다. 이 방식은 포인터 수를 줄이고 비교를 한 노드 안에서 묶어 처리하며, 캐시 지역성을 높여 지연시간을 낮추는 데 목적이 있다.
삽입과 삭제에서 지켜야 할 노드 점유도
노드는 일반적으로 {keys[] 정렬 배열, count, left, right, parent, height/balance}로 구성한다. keys 배열은 고정 또는 반고정 크기로 설계할 수 있다.
점유도는 min_utilization ≤ count ≤ capacity 범위에서 관리한다. 노드가 가득 차면 재분배, 회전, 분리를 사용하고, 키를 삭제한 뒤 점유도가 낮아지면 합병, 회전, 프루닝(pruning)을 적용한다.
탐색은 현재 노드의 최소·최대 키를 기준으로 좌우 하위 트리로 내려가거나, 범위 안에 들어온 키를 노드 내부 이진 탐색으로 찾는 방식이다. 삽입은 대상 노드에 여유가 있으면 배열에 직접 넣고, 공간이 없으면 상·하위 노드 이동 또는 회전·재분배로 수용한다. 삭제 후에는 이웃 노드와의 재분배나 합병, 필요할 경우 회전과 프루닝을 통해 균형을 복구한다.
높이 차이가 2 초과하면 회전을 수행하며, 전후 과정에서 노드 내부 키를 다시 배열해 범위 불변식을 유지한다. 이 회전은 트리 높이를 억제하고 참조 지역성과 경로 길이의 분산에도 영향을 준다.
캐시와 동시성 관점의 설계
한 노드에 여러 키를 저장하면 노드를 따라가는 횟수가 줄고 CPU 캐시 히트율을 높일 수 있다. 키 비교가 노드 경계에서 묶여 이뤄지므로 분기 예측 실패와 메모리 접근의 분산을 줄이는 효과도 기대할 수 있다.
동시성 제어에는 노드 단위 래치 커플링(latch coupling)을 두고, 읽기는 낙관적으로 처리하며 쓰기는 배타적으로 처리하는 방식을 고려할 수 있다. 긴 범위 잠금은 피하는 편이 권장된다. 삭제와 프루닝이 발생하는 구조이므로 Epoch 기반 또는 Hazard Pointer 기반 GC로 레퍼런스 안정성을 보장하는 메모리 회수 방식도 필요하다.
맞는 워크로드와 피해야 할 조건
T-Tree는 키-값 저장소의 포인트 조회와 짧은 범위 조회 중심 트랜잭션을 처리하는 메모리 상주 OLTP 인덱스에 맞는다. 제한된 메모리에서 포인터 수를 줄이고 간결한 동작이 필요한 임베디드 시스템, 짧은 범위 스캔이 빈번하고 갱신 비율이 중간 수준인 읽기 우세 실시간 분석 워크로드도 적용 대상이 될 수 있다.
반대로 수십만 키 이상을 연속으로 읽는 광범위 순차 스캔에는 B+-Tree나 CSS-Tree가 유리한 경향이 있다. 초고도 동시 갱신과 가변 길이 키, 긴 문자열 프리픽스를 다뤄야 한다면 ART나 Masstree 계열을 고려할 수 있다. 최신 CPU에서 깊은 분기와 회전 비용이 병목이 될 때도 캐시 민감 B+-Tree 또는 정렬 배열과 배치 삽입 대안을 함께 검토할 필요가 있다.
포인터 추적이 줄어들면 평균 탐색 경로가 짧아지고, 노드 내부 이진 탐색은 분기 수를 낮출 수 있다. AVL과 비교하면 노드 수가 줄어 메타데이터와 포인터 오버헤드를 절감할 여지도 있다. 키 배열을 연속 메모리에 배치하는 특성은 L1/L2 히트율 상승으로 이어질 수 있다.
다만 효과 크기는 키 크기, 노드 용량, 키 분포, 갱신 비율, CPU 캐시 특성에 좌우된다. 포인트 조회, 짧은 범위 조회, 혼합 워크로드를 대상으로 한 마이크로벤치로 도입 전 검증이 필요하다.
검색과 삽입이 진행되는 경로
인메모리 인덱스 구조별 특성
| 지표 | T-Tree | AVL Tree | B+-Tree(in-memory) |
|---|---|---|---|
| 포인트 조회 지연 | 높음(유리) | 보통 | 보통~높음(구현 의존) |
| 짧은 범위 스캔 | 높음(유리) | 낮음 | 높음 |
| 긴 범위 스캔 | 보통 | 낮음 | 매우 높음(유리) |
| 메모리 오버헤드 | 낮음~보통 | 보통~높음 | 보통 |
| 캐시 지역성 | 높음 | 낮음 | 높음(캐시 민감 변형 시) |
| 동시성 구현 난이도 | 보통 | 낮음 | 높음 |
| 회전/재구성 비용 | 보통 | 보통 | 낮음(분할/병합 위주) |
실제 성능은 구현, 키 분포, CPU/메모리 계층, 워크로드에 따라 달라지므로 최신 정보 확인이 필요하다.
용량과 회수 정책이 만드는 트레이드오프
keys 배열 크기는 1~2개 캐시라인 안에 넣는 원칙을 적용할 수 있으며, 예시는 64B/128B다. 용량을 키우면 트리 높이는 낮아질 수 있지만 오버플로 발생 시 재분배와 회전 비용은 커진다.
래치 커플링은 부모에서 자식 순으로 짧게 보유하고, 읽기가 많은 환경에서는 읽기-쓰기 분리(RWLock)를 적용할 수 있다. 미세 잠금은 경합을 줄이지만 코드 복잡도와 데드락 위험을 높인다.
삭제 시에는 언더플로 임계치를 조정해 과도한 합병과 회전을 막고, 지연 삭제 뒤 배경 컴팩션을 두는 방안도 있다. 즉시 정리와 지연 정리는 일관성 및 메모리 회수 시점에서 차이가 난다.
고정 길이 키와 값은 SoA 또는 배열화로 선형 접근을 최적화할 수 있다. 가변 길이 데이터는 별도 영역에 저장해 노드를 가볍게 유지한다. Epoch/Hazard Pointer를 사용하면 RCU 스타일의 비차단 읽기가 가능하지만, 회수 지연 비용은 감수해야 한다.
교육용 구현으로 보는 기본 동작
전제조건은 Python 3.10+, 단일 스레드, 정수 키이며 균형과 회전은 구현하지 않은 데모 목적의 예시다. 실제 사용에는 회전·재분배, 동시성, GC가 필요하다.
# Python 3.10+
from bisect import bisect_left
class TTreeNode:
__slots__ = ("keys", "left", "right", "parent")
def __init__(self, capacity=8, parent=None):
self.keys: list[int] = []
self.left: "TTreeNode | None" = None
self.right: "TTreeNode | None" = None
self.parent: "TTreeNode | None" = parent
self._cap = capacity
@property
def min(self): return self.keys[0] if self.keys else None
@property
def max(self): return self.keys[-1] if self.keys else None
@property
def full(self): return len(self.keys) >= self._cap
def search(self, key: int) -> bool:
n = self
while n:
if not n.keys:
return False
if key < n.min:
n = n.left
elif key > n.max:
n = n.right
else:
i = bisect_left(n.keys, key)
return i < len(n.keys) and n.keys[i] == key
return False
def insert(self, key: int):
n = self
while True:
if not n.keys:
n.keys.append(key)
n.keys.sort()
return
if key < n.min:
if n.left is None:
n.left = TTreeNode(capacity=n._cap, parent=n)
n = n.left
elif key > n.max:
if n.right is None:
n.right = TTreeNode(capacity=n._cap, parent=n)
n = n.right
else:
# insert into node
if n.full:
# simplistic spill: create left or right child by median
mid = len(n.keys)//2
if key < n.keys[mid]:
if n.left is None:
n.left = TTreeNode(capacity=n._cap, parent=n)
n = n.left
else:
if n.right is None:
n.right = TTreeNode(capacity=n._cap, parent=n)
n = n.right
else:
i = bisect_left(n.keys, key)
if i < len(n.keys) and n.keys[i] == key:
return # dedup
n.keys.insert(i, key)
return
# Demo
root = TTreeNode(capacity=6)
for k in [50, 10, 70, 60, 65, 62, 63, 64, 90, 30, 20, 25]:
root.insert(k)
assert root.search(63) is True
assert root.search(999) is False
print("OK")위 예시는 균형, 회전, 재분배를 단순화했으므로 삽입이 한쪽으로 치우치면 트리 높이가 증가할 수 있다. 실제 엔지니어링에서는 회전 규칙, 언더플로·오버플로 처리, 동시성, 메모리 회수를 구현해야 한다.
벤치마크와 운영 준비
기능 요구에서는 포인트 조회 비중, 짧은 범위 스캔 비중, 메모리 상주 비율 100% 전제를 먼저 확인한다. 성능 검증은 노드 용량을 8/12/16 키로 스윕하고 혼합 워크로드(YCSB A/B/C)로 마이크로벤치를 수행할 수 있다.
운영 환경에서는 탐색 깊이 분포, 회전·재분배 카운터, 노드 점유도 히스토그램을 모니터링하고 온라인 리밸런싱 절차를 준비한다. CSB+-Tree, ART, Masstree, Bw-Tree와 A/B 성능 및 운영 난이도를 비교해 워크로드에 맞는 구조를 결정한다.