@)참고
https://www.cs.usfca.edu/~galles/visualization/BTree.html
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
B-Tree는 데이터베이스(Index)와 파일 시스템에서 널리 사용되는 Balanced Tree 일종이다.
node 의 자식 수 중 최댓값을 K라고 하면, 해당 B-Tree를 K차 B-Tree 라고도 한다.
B-tree 의 조건
1. node의 key의 수가 k개라면, 자식 node의 수는 k+1개이다.
2. node의 key는 반드시 정렬된 상태여야 한다.
3. 자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 나뉘게 된다.
4. root node는 항상 2개 이상의 자식 node를 갖는다. (root node가 leaf node인 경우 제외)
5. M차 트리일 때, root node와 leaf node를 제외한 모든 node는 최소⌈M/2⌉, 최대M개의 서브 트리를 갖는다.
6. 모든 leaf node들은 같은 level에 있어야 한다.
B-Tree 의 데이터는 key 값에 일대일로 존재함
B+Tree 의 데이터는 리프 노드에만 존재하며 리프노드 끼리는 링크드 리스트로 연결되어 있음
