B-Tree, B+ Tree

B-Tree

• Binary Tree(이진 트리)는 부모 노드가 자식 노드를 2개만 가질 수 있는 트리이기 때문에 균형이 맞지 않을 경우(i.g 편향 트리) 순차탐색의 O(N)에 맞먹을 정도로 효율이 떨어진다
• B-Tree는 더 많은 자식을 가질 수 있어 트리의 균형을 맞출 수 있게 되었고 검색 효율도 O(logN)으로 유지할 수 있게 되었다
  • B-Tree는 Balanced Tree를 의미한다
• M차 B-Tree는 하나의 노드가 최대 M개의 자식 노드를 가질 수 있는 트리이다

특징

1. 노드의 자료수가 N개라면 자식의 수는 N+1 이여야 한다
2. 각 노드의 자료는 정렬된 상태여야 한다
3. 루트노드는 2개 이상의 자식 노드를 가져야 한다
4. 루트노드를 제외한 노드는 M/2개 이상의 자료를 가져야 한다 (M/2 ~ M개)
5. 모든 리프 노드는 같은 레벨에 있다
6. 자료는 중복되지 않는다

B+ Tree

• B-Tree의 확장 개념이다
• 모든 노드에 key, data가 있는 B-Tree와 다르게 비단말 노드에는 key만 존재하며 리프 노드에만 key, data가 모두 있고 리프노드끼리 연결리스트로 연결되어 있다

B-Tree vs B+ Tree

구분	B-Tree	B+ Tree
데이터 저장	리프노드, 비단말노드에 모두 저장	리프노드에만 저장
트리의 높이	높음	낮음
풀 스캔시	모든 노드탐색	리프 노드에서 선형탐색
키 중복	X	O(리프 노드에 모든 데이터가 있어서)
검색	루트노드에 가까울수록 빠름	리프노드까지 가야 데이터가 존재
링크드 리스트	X	리프노드끼리 링크드리스트로 연결