: Self-balancing tree 중 하나. 데이터베이스나 파일 시스템에서 사용되는 것으로 유명.
한 블럭에 많은 데이터를 저장한다는 것이 큰 장점.
- 한 블럭이 1024 Byte라고 한다면 2Byte를 읽으나 1024Byte를 읽으나 입출력 1회 발생하는 비용은 같기 때문
규칙
- 정렬된 상태이다.
- 자식 노드 수가 적어도 2개 이상이다.
- 자식 노드의 수를 최대 M개 가질 수 있을 때 M차 B-tree라고 말한다.
- 자식 노드가 M개 일 때 부모 노드의 key 값은 M-1개이다.
- Root를 제외한 모든 노드는 적어도 M/2개의 데이터를 갖는다.
삽입과 삭제
: 삽입 삭제 시 위의 규칙들을 전부 만족하는지를 체크한다.
- 삽입: 만족이 되지 않는 경우 자식 노드를 추가한다. 특히, 균형을 맞춰가며 재구성한다.
- 삭제: 만족이 되지 않는 경우 비어있는(M/2 이하의 데이터를 갖는) 노드는 sibling 노드와 합쳐지고 다시 조건이 만족되는지를 검사한다.
B+Tree
- B-Tree의 변형 구조이다.
- leaf로 가는 경로 안내만 수행하는 non-leaf node가 존재한다.
- leaf 노드끼리는 연결리스트로 연결되어있다.
- DB indexing의 자료구조로 사용된다고 유명.
- 장점: DB indexing에서 hash table을 사용하지 않는 이유로 범위 탐색(쿼리에서의
where ~~절)을 이야기 하는데, B+Tree에서는 실 데이터인 Leaf node들간 연결리스트로 연결되어있어서 범위 탐색에 유리 - 단점: 항상 leaf까지 내려가야 찾고자 하는 데이터에 도달한다. (log N)
Reference)
https://en.wikipedia.org/wiki/B-tree
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/B%20Tree%20%26%20B%2B%20Tree.md