File-backed B+ Tree

Python으로 구현한 디스크 기반 B+ 트리입니다. 트리와 노드를 메모리에 모두 올리지 않고, 탐색 경로에 필요한 노드만 인덱스 파일에서 읽어 삽입, 삭제, 단일 키 검색, 범위 검색을 수행합니다.

실행 환경

• Python 3.11.6
• 표준 라이브러리: argparse, csv, math, pickle
• 원 보고서의 개발 환경: macOS

별도의 외부 패키지는 필요하지 않습니다.

빠른 시작

# 최대 자식 수(degree)가 10인 인덱스 생성
python bptree.py -c index.dat 10

# CSV 데이터 삽입
python bptree.py -i index.dat input.csv

# CSV에 지정된 키 삭제
python bptree.py -d index.dat delete.csv

# 단일 키 검색
python bptree.py -s index.dat 6259

# 2000 이상 2200 이하의 키 범위 검색
python bptree.py -r index.dat 2000 2200

인덱스 파일명과 CSV 파일명은 자유롭게 지정할 수 있습니다.

입력 형식

삽입용 CSV는 헤더 없이 한 줄에 key,value를 기록합니다.

10,100
25,250
42,420

삭제용 CSV는 헤더 없이 삭제할 키를 한 줄에 하나씩 기록합니다.

10
42

키와 값은 정수로 변환됩니다. 동일한 키는 중복 삽입하지 않습니다.

명령어

기능	명령어	설명
인덱스 생성	python bptree.py -c <index_file> <degree>	최대 자식 수를 지정해 새 트리를 생성합니다.
삽입	python bptree.py -i <index_file> <data_file>	CSV의 key,value 쌍을 삽입합니다.
삭제	python bptree.py -d <index_file> <data_file>	CSV에 적힌 키를 삭제합니다.
단일 검색	python bptree.py -s <index_file> <key>	탐색 경로의 내부 노드 키와 검색 결과를 출력합니다.
범위 검색	python bptree.py -r <index_file> <start_key> <end_key>	닫힌 구간 [start_key, end_key]의 key,value를 출력합니다.

단일 검색에서 키가 없으면 NOT FOUND가 출력됩니다.

설계

주요 클래스

Node는 하나의 노드를 표현합니다.

• degree: 최대 자식 노드 수
• offset: 인덱스 파일에서 노드가 저장된 위치
• keys: 정렬된 키 배열
• pointers: 내부 노드에서는 자식 노드의 파일 오프셋, 리프 노드에서는 값 배열
• next: 다음 리프 노드의 파일 오프셋
• isLeaf: 리프 노드 여부
• parent: 부모 노드의 파일 오프셋

BplusTree는 트리 전체의 메타데이터와 연산을 관리합니다.

• root: 루트 노드 또는 루트의 파일 오프셋
• degree: 최대 자식 노드 수
• nodeOffset: 노드 하나가 차지하는 고정 크기

주요 함수

구분	함수	역할
노드 I/O	load_from_file(offset)	지정한 오프셋에서 노드를 읽습니다.
노드 I/O	save_to_file()	기존 위치에 변경된 노드를 덮어씁니다.
노드 I/O	write_to_file()	파일 끝의 다음 고정 슬롯에 새 노드를 저장합니다.
탐색	find_next_route_node(key)	내부 노드에서 다음 탐색 노드를 결정합니다.
분할	split_leaf_node()	오버플로가 발생한 리프 노드를 분할합니다.
분할	split_non_leaf_node()	오버플로가 발생한 내부 노드를 분할합니다.
병합	merge_leaf_node(siblingNode)	인접 리프 노드를 병합합니다.
병합	merge_non_leaf_node(siblingNode)	인접 내부 노드를 병합합니다.
트리 연산	insert(key, value)	키와 값을 삽입하고 필요하면 상위 노드를 분할합니다.
트리 연산	delete(key)	키를 삭제하고 재분배 또는 병합으로 최소 크기를 복구합니다.
키 보정	arrange_key(modifiedNode)	하위 트리의 최소 키 변경을 상위 구분 키에 반영합니다.

인덱스 파일 구조

• 파일 형식: .dat
• 0-511 byte: 루트 위치, degree 등 B+ 트리 메타데이터
• 512 byte 이후: 직렬화된 노드를 고정 크기 슬롯에 연속 저장
• 노드 슬롯 크기: 512 + 32 * degree byte

노드 안의 실제 키와 포인터 수가 달라져도 파일 위치를 안정적으로 참조할 수 있도록 슬롯 크기를 고정합니다. 데이터는 Python pickle로 직렬화되므로 신뢰할 수 없는 인덱스 파일을 열어서는 안 됩니다.

알고리즘

삽입

1. 루트부터 필요한 노드만 파일에서 읽어 적절한 리프 노드를 찾습니다.
2. 리프에 키와 값을 정렬된 상태로 삽입합니다.
3. 리프에 오버플로가 발생하면 왼쪽에 최소 수의 데이터를 남기고 새 오른쪽 리프로 분할합니다.
4. 리프의 next 연결과 부모 포인터를 갱신하고 새 노드를 부모에 삽입합니다.
5. 부모에도 오버플로가 발생하면 내부 노드를 분할하며 위로 전파합니다.
6. 루트가 분할되면 두 노드를 자식으로 갖는 새 루트를 만듭니다.

삭제

1. 대상 키가 있는 리프를 찾아 삭제하고, 필요하면 상위 구분 키를 갱신합니다.
2. 최소 크기를 만족하면 종료합니다.
3. 언더플로가 발생하면 먼저 여유가 있는 오른쪽 또는 왼쪽 형제에서 항목을 재분배받습니다.
4. 재분배할 수 없으면 형제와 병합하고 부모의 자식 포인터와 구분 키를 제거합니다.
5. 부모가 최소 크기를 위반하면 내부 노드에서도 자식 포인터 단위의 재분배 또는 병합을 반복합니다.
6. 부모가 하나의 자식만 남기면 그 자식을 새 루트로 올립니다.

단일 키 검색

1. 내부 노드의 구분 키를 따라 대상 키가 위치할 리프까지 내려갑니다.
2. 방문한 각 내부 노드의 키를 출력합니다.
3. 리프를 선형 탐색해 값을 출력하며, 키가 없으면 NOT FOUND를 출력합니다.

범위 검색

1. start_key가 위치할 리프를 찾습니다.
2. 리프에서 범위에 포함되는 key,value를 순서대로 출력합니다.
3. 현재 리프의 마지막 키가 end_key보다 작으면 next 포인터로 다음 리프를 읽습니다.
4. end_key보다 큰 키를 만나면 탐색을 종료합니다.

검증 내용

원 보고서에서는 다음 시나리오로 동작을 확인했습니다.

• 삽입과 삭제의 주요 분기 조건을 포함하는 기본 데이터셋
• 중복 없는 1,000개 데이터: value = key * 10으로 구성해 단일 검색과 범위 검색 결과 확인
• 10,000개 데이터: 삽입, 단일 검색, 범위 검색 및 일부 키 삭제 후 결과 확인
• 1,000,000개 데이터 규모: 삽입과 삭제 후 범위 검색 결과 확인, 삽입은 보고된 환경에서 약 40초 소요

테스트에서는 범위 검색 결과가 키 순서대로 출력되고, 삭제한 키만 결과에서 제외되는 것을 확인했습니다. 실행 시간은 하드웨어와 저장장치 성능에 따라 달라질 수 있습니다.