[ADV_db]Chap 3. Indexing - B+tree 검색,삽입,삭제

---

# B+Tree 검색

---

루트 노드부터 검색하는 key값인 v보다 큰 key값이 나올 때까지 검색하다 같은 key값을 가지면, P(i+1)로 아니면 P(i)로 가서 리프 노드가 될 때까지 반복한다.

• 하나의 노드는 보통 하나의 디스크 블록 사이즈인 4kb로 한다. 따라서 보통 하나의 index당 크기는 40byte로 정하고 Fanout n은 100정도로 하는 게 보통이다.
• 그럼 key가 백만개 있다고 가정했을 때, log50(1,000,000) = 4 이므로 검색할 때마다 4개의 노드를 지난다.

Composite key(복합키)

• 만약 key가 primary key가 아닌 경우, 유일성을 보장하기 어렵다. 이런 경우, (ai , Ap)식으로 복합키를 만들어 유일성을 보장할 수 있다.
• 하지만, 이러면 더 많은 I/O가 필요하다. 특히 non clustering 된 경우에는 매번 I/O가 필요하다.

---

# B+Tree 삽입

---

B+Tree 삽입 과정 개요

• 검색 과정을 통해 삽입해야 할 리프 노드를 찾는다.
• 리프 노드 자리가 남아 있으면, 그냥 삽입하면 되지만 자리가 남아 있지 않다면 Split과정을 거쳐야한다. 그리고 이를 부모 노드들에도 반영시켜야 한다.

Leaf Node Split 과정

• 일단, 새로 넣을 키 값을 포함하여 정렬하고, ⌈n/2⌉ 개는 두고 나머지를 새로운 노드로 만든다.
• 새로 만들어진 노드의 첫 번째 키 값을 부모 노드에 복사한다. 최악의 경우 모든 부모가 다 차 있으면 루트 노드가 Split해야하고, 그럼 높이가 1 높아진다.

Non Leaf Node Split 과정

• 리프 노드 Split 과정과 동일하지만, 새로 만들어진 노드의 첫 번째 키 값을 복사가 아닌 잘라서 부모 노드에 삽입한다.

---

# B+Tree 삭제

---

B+Tree 삭제 과정 개요

• 검색을 통해 삭제할 키와 포인터를 찾고, 삭제한다.
• 만약 해당 노드의 수가 최소 키 개수보다 작아진 경우 같은 레벨의 노드들과 Merge 해야한다.
  • 하지만, 만약 다른 노드들과 Merge하기에는 다른 노드들이 어느정도 차있어서 불가능한 경우에는 Redistribution를 통해 조건을 만족시켜야한다.
• 그리고 부모 노드에서 해당 노드를 가르키던 키 값과 포인터를 삭제하거나 갱신한다.
• 만약 삭제 이 후, 루트 노드에 포인터 하나만 남게 된다면, 그 자식을 루트로 하고 삭제한다.

Non Leaf Node Redistribution 과정

• 리프 노드가 아닌 경우에는 키 값이 부족하다고 노드를 삭제하거나 바로 Merge할 수 없기 때문에 부모 노드와 키 값을 재분배한다.
• 아래의 경우는 맨 자식 노드는 하나로 Merge되었지만 부모가 삭제되었고 동시에 다른 부모가 Merge할 수 없는 경우다.
  • 이런 경우 왼쪽 부모 노드를 Split하여 오른쪽 트리를 형성 하도록 하는 방식이다.

• 아래의 경우는 부모노드가 삭제되었지만, 자식노드이 남아있고 동시에 다른 부모가 Merge할 수 있는 경우다.
  • 이런 경우, 조부모 노드(?)에서 제일 작은 키 값을 가져와서 남아있던 자식 노드를 입양한다.
   

After deletion of "Gold"

---

#  이슈

---

Update 복잡도

• O(log⌈n/2⌉(K))
• 실제로는 리프 노드들을 제외한 인덱스 노드들은 버퍼에 저장되어 있어, I/O작업이 훨씬 수월하다.
• 대부분의 작업은 리프 노드에서 일어나고, Split이나 Merge가 일어나는 횟수가 적다. 
• 리프 노드의 점유율은 평균적으로 삽입 순서에 따라 다른데
  • 랜덤인 경우 2/3
  • 순차적으로 삽입된 경우 1/2

Non unique search key

• 리프 노드에 Bucket형태로 같은 Search key를 가지는 모든 레코드들의 포인터를 저장하게 할 경우
  • 공간을 효율적으로 사용할 수 있다.
  • 정해지지 않은 Bucket사이즈에 대한 이슈가 있다.
• 레코드마다 Search key를 저장할 경우
  • Split을 하기 너무 복잡하게 되버려 같은 Search key를 가지는 리프노드가 여러 개일 수 있다.
  • 공간 사용이 비효율적이다.
• 중복 키에 대한 문제는 상당히 복잡하므로, 대부분의 데이터베이스 시스템에서는 겹치는 Search key의 경우 다른 걸 추가해서라도 Unique하게 만든다.