btree-cr

Crystal로 구현한 디스크 기반 B+트리 인덱스 엔진. 고정 크기 페이지와 LRU 캐시를 사용해 메모리보다 큰 데이터셋도 안정적으로 저장하고 범위 쿼리를 지원한다.

왜 B+트리인가

B+트리는 데이터베이스와 파일시스템에서 널리 쓰이는 정렬 인덱스 구조다. 일반 B트리와 달리 값은 리프 노드에만 저장하고 내부 노드는 라우팅만 담당한다. 이런 특징이 주는 장점은 다음과 같다.

• 내부 노드의 팬아웃이 크다: 값이 없으므로 한 페이지에 더 많은 키를 담을 수 있고, 트리 높이가 낮아진다. 높이가 낮으면 디스크 I/O 횟수가 줄어든다.
• 범위 스캔이 빠르다: 리프 노드가 연결 리스트로 묶여 있어, 범위 쿼리를 리프만 따라 순회하면 된다. 루트로 되돌아갈 필요가 없다.
• 일관된 접근 비용: 모든 리프가 같은 깊이에 있어 어떤 키든 동일한 수의 페이지 접근으로 도달한다.

페이지 구조

모든 노드는 page_size 바이트(기본 4096)의 고정 크기 페이지에 저장된다. 페이지는 1부터 시작하는 PageId로 번호가 매겨지며, 파일 오프셋은 (page_id - 1) * page_size로 계산된다. PageId 0은 널 페이지로 예약되어 있다.

메타 페이지

1번 페이지는 메타 페이지로 예약된다. 트리의 루트 페이지 id를 여기에 저장하여 엔진을 다시 열 때 분할로 인해 루트가 바뀌었어도 올바른 루트를 찾을 수 있다.

+--------+--------+--------+--------+--------+--------+--------+--------+
| 매직(0x42545245 "BTRE", UInt32 LE) | 루트 PageId(UInt32 LE)            |
+--------+--------+--------+--------+--------+--------+--------+--------+
  오프셋 0            4            8

나머지 바이트는 0으로 채워진다. 매직 값이 일치하지 않으면 손상된 파일로 간주해 예외를 발생시킨다.

+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
| 타입   | 슬롯 개수(UInt32 LE) | 다음 리프/첫 자식(UInt32 LE) | 슬롯 영역 ...            |
| 1바이트|       4바이트        |          4바이트             |                          |
+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
  오프셋 0       1            5            9

• 타입: 0 = 리프 노드, 1 = 내부 노드
• 슬롯 개수: 리프면 키-값 쌍 수, 내부 노드면 키 수
• 다음 리프/첫 자식: 리프 노드는 다음 리프의 PageId, 내부 노드는 첫 번째 자식의 PageId

리프 노드 슬롯

+-----------+-----------+--------+--------+
| 키 길이   | 값 길이   | 키     | 값     |
| UInt16 LE | UInt16 LE |        |        |
+-----------+-----------+--------+--------+

내부 노드 슬롯

+-----------+----------------+--------+
| 키 길이   | 자식 PageId    | 키     |
| UInt16 LE | UInt32 LE      |        |
+-----------+----------------+--------+

맨 왼쪽 자식은 헤더의 "다음 리프/첫 자식" 필드에 별도 보관된다. 나머지 자식은 각 키 슬롯과 1:1로 짝을 이룬다. n개의 키에 n+1개의 자식이 있다.

모든 정수는 little-endian으로 직렬화하여 엔디안 독립성을 보장한다.

디스크 I/O 모델

이 엔진은 페이지 단위로 파일을 읽고 쓴다. 한 번의 read/write 호출이 곧 한 페이지의 디스크 I/O에 대응된다. 트리 연산의 I/O 비용은 다음과 같이 모델링할 수 있다.

• 조회: 루트에서 리프까지 내려가며 한 페이지씩 읽는다. 트리 높이를 h라 하면 h번의 페이지 읽기가 발생한다.
• 삽입: 조회 경로 h번 읽기 + 분할이 일어나면 추가 쓰기. 최악의 경우 루트까지 분할이 전파되어 h + O(h)번의 쓰기.
• 삭제: 조회 경로 h번 읽기 + 언더플로우 시 형제 읽기/쓰기.
• 범위 스캔: 시작 리프까지 h번 읽은 뒤, 리프 연결 리스트를 따라 순회. k개의 리프를 방문하면 h + k번의 읽기.

LRU 캐시

Pager는 페이지 캐시를 두어 자주 접근하는 페이지의 디스크 I/O를 줄인다. 캐시 용량(cache_capacity)을 초과하면 가장 오래 사용되지 않은 페이지를 방출한다. 방출 시 더티 상태면 디스크에 기록한다. 루트와 상위 내부 노드들은 거의 항상 캐시에 머물므로 실제 I/O는 트리 높이보다 훨씬 적다.

사용법

설치

shard.yml에 추가:

dependencies:
  btree-cr:
    github: dogskip/btree-cr

기본 예제

require "btree-cr/src/engine"

config = EngineConfig.new
config.leaf_order = 64
config.internal_order = 128

engine = BTreeEngine.new("index.db", config)

# 삽입
engine.put("user:001".to_slice, "Alice".to_slice)
engine.put("user:002".to_slice, "Bob".to_slice)

# 조회
value = engine.get("user:001".to_slice)
puts value.try { |v| String.new(v) } # => Alice

# 범위 스캔
cursor = engine.range("user:000".to_slice, "user:999".to_slice)
cursor.each do |key, val|
  puts "#{String.new(key)} => #{String.new(val)}"
end

# 삭제
engine.delete("user:002".to_slice)

engine.close

설정 항목

모듈 구성

• src/btree_engine.cr — 공통 타입(PageId, BtKey, BtValue, Compare, EngineConfig)
• src/pager.cr — 페이지 관리자. 파일 I/O와 LRU 캐시.
• src/node.cr — 리프/내부 노드의 직렬화/역직렬화와 기본 연산.
• src/btree.cr — B+트리. 삽입/삭제/조회, 분할/병합, 범위 수집, 메타 페이지 관리.
• src/cursor.cr — 범위 스캔 커서. 정방향/역방향.
• src/engine.cr — BTreeEngine 진입점. 위 모듈을 묶어 단일 API 제공.

테스트

crystal spec

테스트는 노드 직렬화, 페이지 관리자, 트리 삽입/삭제/분할/병합, 범위 쿼리, 대량 데이터 시나리오를 다룬다.

라이선스

MIT. 자세한 내용은 LICENSE 파일 참고.