B-트리의 귀환 — 빠르고 페이지화 가능한 노드 레이아웃 설계

AI 요약

Technical University of Munich 연구진은 가변 길이 키를 직접 저장하는 페이지 기반 B-트리를 구현하고, 노드 내부 탐색과 저장 방식을 바꾸는 최적화 여섯 가지를 평가합니다. 연구의 배경은 메모리 용량보다 데이터가 커지는 시스템입니다. 이런 환경에서는 메모리에서 대부분의 작업을 처리하면서 플래시 저장장치로 자연스럽게 넘어갈 수 있어야 합니다. 메모리 전용 인덱스와 달리 B-트리는 페이지 단위 저장에 적합하지만, 가변 길이 키를 다루는 구현과 비교 자료는 충분하지 않았습니다.

노드 레이아웃 최적화

기준 구현은 키와 값을 페이지 안에 저장하고, 정렬된 슬롯 배열로 검색합니다. 연구진은 여기에 접두사 절단(prefix truncation), 키 앞부분 복사(heads), 힌트 배열(hints), 지문(fingerprinting), 반조밀 리프(semi dense leaves), 완전 조밀 리프(fully dense leaves)를 적용합니다.

접두사 절단은 한 노드의 키가 하한·상한 경계 키와 공유하는 접두사를 저장하지 않습니다. URL 키에서는 평균 49바이트를 줄였고, 노드당 레코드가 늘면서 스캔 처리량도 개선했습니다. 키 앞 4바이트를 슬롯에 복사하는 heads는 키 비교 때 임의 메모리 접근을 줄입니다. 조회와 삽입 처리량을 16~64% 높였지만, 레코드당 공간을 늘립니다. 힌트 배열은 슬롯 일부의 키 앞부분을 따로 저장해 이진 탐색 범위를 좁힙니다. 정수 키 조회는 25~26% 빨라졌고, 문자열에서는 개선 폭이 작거나 삽입 비용이 생겼습니다.

Fingerprinting 리프는 키의 1바이트 해시를 SIMD로 비교해 후보를 찾고, 삽입 때 정렬을 미룹니다. 문자열 키 조회는 13~22% 빨라졌지만 정수 키에는 불리했습니다. 스캔 전에 정렬해야 하는 점도 스캔 처리량을 낮춥니다.

조밀 리프는 키가 연속된 정수에 가까울 때 비교 대신 배열 위치로 레코드를 찾습니다. 반조밀 리프는 슬롯마다 값의 위치를 저장하고, 완전 조밀 리프는 같은 크기의 값들을 연속 배열에 둡니다. 100% 밀도 정수 키에서 완전 조밀 리프는 힌트 배열 방식보다 조회 71%, 삽입 213%, 스캔 105% 높은 처리량을 보였습니다. 공간 사용량은 레코드당 52% 줄었습니다. 다만 완전 조밀 방식은 빈 슬롯 비용이 커서 키 밀도가 충분히 높아야 이득입니다. 여러 구간에서 순차 생성한 ID 삽입에서는 완전 조밀 리프가 힌트 배열보다 최대 약 2.7배 높은 삽입 처리량을 기록했습니다.

적응형 B-트리와 평가

한 가지 레이아웃이 모든 키와 작업에 최선은 아닙니다. 연구진은 노드 분할·병합 때 키 앞부분의 중복 정도를 살펴 문자열형 키에 적합한지 판단하고, 읽기 작업 중 조회와 스캔 비율을 세는 작은 카운터로 레이아웃을 고릅니다. 조밀 키에는 완전 조밀 리프를 우선 적용합니다. 선택 결과는 대부분의 키·작업 조합에서 더 빠른 두 후보의 처리량 98% 이상에 도달했습니다. 위키 제목 스캔은 레이아웃 변경이 늦어져 8% 낮았지만, 작업 횟수를 늘리자 차이가 2%로 줄었습니다.

평가는 AMD Ryzen 9 7950X에서 URL, 위키 제목, 조밀·희소 32비트 정수 키를 사용해 수행했습니다. 연구진은 기준 B-트리가 인메모리 구조 Wormhole보다 조회 성능이 낮지만, 최적화를 적용하면 성능 격차를 절반으로 줄이고 조밀 정수 키에서는 앞설 수 있다고 보고합니다. 또 적응형 B-트리를 다중 스레드·아웃오브메모리 저장 엔진 vmcache에 통합해 시스템 수준 성능도 확인합니다. 고정된 4KiB 노드 크기를 유지해 페이지 캐싱을 지원하는 점도 설계 목표입니다.

원문: Proceedings of the ACM on Management of Data / 번역·요약: Trawling