[ADV_db]Chap 3. Indexing - B+Tree 소개

---

# B+Tree

---

B+Tree vs Sequential index

	B+Tree	Sequential index
장점	1. 삽입,삭제 과정에서 알아서 재구성이 일어난다. 2. 성능 유지를 위한 전체 파일 재구성이 필요하지 않다.	1. 쉽다 ㅋ
단점	삽입,삭제 과정이 좀 더 오래 걸리고, 트리를 저장할 추가 공간이 필요하다.	1. Overflow Block때문에 파일이 커질수록 성능이 떨어진다 2. 주기적으로 재정비가 요구된다.

B+Tree 특징

• B+tree에서의 모든 데이터는 리프 노드에 들어있거나, 그 주소가 저장되어 있다. 따라서 리프 노드를 제외한 노드를 "인덱스 노드"라 부르고, 리프 노드를 "데이터 노드"라 부른다. 
• 모든 리프 노드는 연결리스트로 연결되어 있고, 순서대로 정렬되어 있다. 그리고 모든 리프 노드는 같은 레벨에 있다.
• 노드마다 가질 수 있는 포인터의 개수를 Fanout이라고 부르고 여기서는 Fanout을 n이라고 치겠다.
• 모든 노드는 ⌈(n–1)/2⌉ ~ n-1개 까지의 key값을 가질 수 있다. 포인터의 개수는 ⌈n/2⌉ ~ n개까지 가질 수 있다.
  • Root 노드는 리프 노드일 때는 0부터 n-1개의 키값을 가질 수 있고, 리프 노드가 아닐 때는 최소 2개 이상의 키값을 가지고 있어야 한다.
• 모든 노드는 포인터로 연결되어 있기 때문에 물리적으로 가까이 있지 않아도 된다.
• 검색할 때 매우 효율적이다.( ⌈log⌈n/2⌉(K)⌉)

Non-leaf Node in B+Tree

• P1 포인터가 가르키고 있는 노드의 모든 키값은 K1보다는 작고, Pn이 가르키는 노드의 키값들은 k(n-1)보다 크거나 같다.
• Pi가 가르키고 있는 노드의 키 값들은 K(i-1)보다 크거나 같고 Ki보다는 작다.