B 트리(B-Tree)

B 트리(B-Tree)

B-Tree

이진트리는 하나의 부모가 두개의 자식밖에 갖지 못하고, 균형이 맞지 않으면 검색 효율이 선형(O(N)) 으로 떨어진다.

으로 떨어진다. 하지만 이진트리가 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN) 으로 보이는 장점이 있다.

Abstract

DB, 파일시스템에서 널리 쓰이는 트리 자료구조의 일종

이진트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree

자식수에 대해 일반화를 진행하면서, 하나의 레벨에 자식을 더 많이 저장하는 것이 아니라 트리의 균형을 자동으로 맞추는 로직까지 구현

단순하고 효율적, 레벨로만 따지만 완전히 균형을 맞춘 트리

멀티레벨 인덱싱을 통해 빠른 검색이 가능

규칙

M차 B 트리 ➡️ 최대 M개의 자식 을 가질 수 있는 B 트리

루트노드는 적어도 2개 이상의 자식을 가져야함 루트노드를 제외한 모든 노드는 M/2개 부터 최대 M개의 자식을 가짐 노드에는 최소 [M/2]-1개 부터 최대 M-1개의 키를 포함 노드의 자료수(key)가 x개라면, 자식수는 x+1개여야함 최소 차수는 자식수의 하한값 을 의미, 최소 차수가 t라면 M = 2 * t - 1 (최소차수 t가 2라면 M = 3차 B 트리, key의 하한은 1개)

각 노드의 자료는 정렬된 상태여야함 (정렬된 순서를 보장)

외부 노드(External Node)로 가는 경로의 길이는 모두 같음 모 든 leaf node는 동일한 level을 가짐

입력 자료는 중복될 수 없음

e.g.) 3차 B 트리

Key 탐색, 삽입, 삭제과정 추가예정

참고한곳

from http://nooblette.tistory.com/313 by ccl(A) rewrite - 2021-12-24 20:00:54