B-트리
•
이진트리를 확장한 트리이다.
•
하나의 노드가 가질 수 있는 자식노드의 갯수가 여러개(쵀대 숫자가 2이상)인 트리 구조를 의미
•
대량의 데이터를 메모리가 아닌 디스크에서 효율적으로 읽고 쓰기 위해 설계되었다.
B-트리의 특징
•
균형트리이다.
•
모든 리프 노드가 같은 위치를 갖고 있게 설계되어 있다.
•
따라서 검색에 걸리는 시간이 일정하다.
•
노드가 꽉 찰 때 분할하고, 특정 수준 이하로 내려가면 병합한다.
•
B+, B*, B# 등 다양한 변형이 존재한다.
B-트리의 구조
•
루트 노드
◦
최상단 노드
•
브랜치 노드 (내부 노드 - 인터널 노드)
◦
루트, 리프 노드를 제외한 모든 노드
◦
자식 노드를 가리키는 포인터와 키 값을 포함한다.
•
리프 노드
◦
자식이 없는 최하단의 노드
◦
실제 데이터를 포함하며, 모든 리프 노드는 같은 레벨에 있다.
B-트리의 연산
•
검색 (Search)
◦
루트 노드부터 시작해 키 값을 비교하며 적절한 리프 노드로 내려간다.
1.
루트 노드에서 시작하여 검색하려는 값과 노드의 값의 대소비교를 한다.
2.
노드의 값보다 검색값이 작으면 왼쪽 자식으로 이동
노드의 값보다 검색값이 크면 오른쪽 자식으로 이동
3.
이를 반복하며 검색값을 가진 노드를 발견시 종료
•
삽입 (Insertion)
◦
새로운 키를 적절한 위치에 삽입하고, 필요한 경우 노드를 분할한다.
과정
•
삭제 (Deletion)
◦
키를 삭제하고, 필요한 경우 노드를 병합하거나 재배치한다.
