T-Tree로 설계하는 메모리 기반 데이터베이스 인덱스

메모리 인덱스에서 T-Tree가 겨냥한 지점

메모리 기반 데이터베이스는 디스크 I/O 지연 없이 데이터에 접근할 수 있지만, 인덱스가 사용하는 메모리와 탐색 경로의 비용은 여전히 설계 대상이다. T-Tree는 이 환경에서 범위 검색과 삽입·삭제를 다루기 위해 만든 균형 이진 검색 트리다.

AVL 트리의 균형 유지 특성과 B-트리의 노드 내 다중 키 저장 방식을 함께 사용한다. 디스크 블록에 맞춘 B-트리와 달리, CPU 캐시 적중률과 메모리 접근 횟수를 고려하는 구조라는 점이 출발점이다.

T-Tree의 노드는 하나의 키만 갖는 일반적인 이진 검색 트리 노드와 달리 여러 키와 데이터를 보관한다. 포인터 수를 줄일 수 있고, 노드 내부의 키를 순서대로 다루므로 범위 쿼리에도 유리하다.

트리 전체는 AVL 방식으로 좌우 서브트리의 균형을 유지한다. 삽입이나 삭제 뒤 균형 인덱스를 조정해 탐색 시간을 보장하며, 순차 접근이 필요한 범위 검색에서 강점을 갖는다.

각 노드가 다수의 키를 담고 AVL 규칙으로 균형을 유지하므로, 메모리 접근을 줄이고 CPU 캐시 효율을 높이는 데 초점을 맞춘다.

비교 항목	T-Tree	B-Tree	AVL Tree
검색 속도	매우 빠름 (AVL 기반 균형)	빠름 (디스크·메모리 모두 안정적)	매우 빠름 (높은 균형도)
삽입/삭제 성능	빠름 (노드 단위 저장으로 재구조화 최소화)	중간 (노드 분할·병합 발생)	느림 (균형 유지 회전 빈번)
메모리 효율성	높음 (노드에 다중 키 저장)	중간~낮음 (디스크 블록 최적화 중심)	낮음 (포인터/메타데이터 과다)
범위 검색 성능	매우 우수 (순차 접근 최적화)	우수 (노드 순차 탐색)	보통 (순차 접근 비효율)
적용 환경	메모리 기반 DB, 실시간 처리	디스크 기반 DB, 범용 인덱스	메모리 기반 고속 탐색

T-Tree는 메모리 기반 환경에서 범위 검색과 메모리 효율성에 특히 강점이 있다. 반대로 디스크 중심 시스템에서는 B-Tree가 여전히 우위다.

키가 들어갈 범위의 노드를 찾은 뒤, 노드에 여유가 있으면 내부 정렬 상태를 유지하며 삽입한다. 공간이 부족하면 키를 재배치하며 노드를 분할한다. 해당 위치를 찾지 못한 경우에는 전임자 또는 후임자 위치를 기준으로 새 리프 노드를 만들고 부모 포인터를 연결한다.

이후 AVL 균형 조건을 확인하고, 불균형이 발생하면 회전을 적용한다. 마무리 단계에서는 높이와 균형 정보를 갱신한다.

삭제 대상 노드에 여러 키가 있으면 정렬 상태를 유지한 채 해당 키만 제거할 수 있다. 단일 키 노드라면 형제 노드에서 경계 키를 차용하거나, 차용할 수 없을 때 병합하고 부모의 구분 키를 조정한다.

그 다음 균형 계수를 확인해 필요하면 AVL 회전을 수행한다. 높이와 균형 정보뿐 아니라 노드 경계 키도 최종적으로 갱신해야 한다.

키 정렬 방식은 고정하고 모든 노드에 같은 비교자를 적용해야 한다. 분할과 병합에서는 최소·최대 키 경계를 반드시 갱신한다. 회전 뒤에는 부모 링크와 서브트리의 최소·최대 키 메타데이터도 동기화해야 한다.

노드 풀(node pool)이나 슬랩 할당자를 사용하면 메모리 파편화를 줄이는 데 도움이 된다.

T-Tree는 Oracle TimesTen과 연구용 MMDB 같은 메모리 기반 데이터베이스에서 활용할 수 있다. 빠른 범위 쿼리와 빈번한 갱신이 함께 일어나는 실시간 검색 시스템, 인메모리 인덱스 최적화가 필요한 트랜잭션 처리 시스템도 적용 대상이다.

디스크 기반 인덱스가 메모리 환경에서 보이는 비효율을 줄이고자 할 때, T-Tree는 범위 검색 성능, 메모리 사용 효율, 삽입·삭제의 안정성을 함께 검토할 수 있는 선택지다.