[ADV_db]Chap 3. Indexing - B+Tree 추가내용들

---

# B+tree Extensions

---

B+Tree File Organization

• 리프 노드에 포인터가 아닌 레코드 자체를 저장하는 방식
• 삽입/삭제/갱신이 일어나더라도 항상 Clustered된 상태를 유지하게 해준다.
• 레코드가 포인터보다 사이즈가 크기 때문에 리프 노드에 들어가는 레코드의 최대 수는 리프 노드가 아닌 노드들의 포인터 수보다 작을 수 밖에 없다.
• 따라서 공간 활용도가 중요한데 이를 위해서 가능한 많은 Siblings를 Split/Merge에 포함시키게 된다. 
  • 그 결과 m개의 sibling노드가 재분배에 참여한다면 각 노드마다 최소⌊(m-1)n/m⌋개의 엔트리를 가지게 된다.

• 하지만 이 경우 리프 노드에 있던 레코드가 노드 사이즈보다 커져서 Split을 해야한다면, 레코드를 이동 시키는 비용은 너무 비싸다.
• 따라서, 리프노드가 아닌 노드에 포인터 대신 key값을 추가하여 리프 노드에서 Split이 일어나더라도 index 노드들에는 갱신이 필요없도록 만들 수 있다.
  • 아니면 만약 key값이 Unique하지 않다면 다른 속성을 추가해서 Unique하도록 만드는게 좋다.
  • 이렇게 하면 쿼리 하는게는 좀 더 시간이 걸리겠지만, 데이터 갱신에는 더 적은 시간이 걸리게 된다.

Index Strings

• 키 값으로 문자열을 사용하는 방식
• 노드의 사이즈가 정해져있기 때문에 문자열의 크기를 알 수 없으므로 Fanout을 정해둘 수 없다.
  • 따라서, 문자열이 길어질 수록 Fanout이 작아져 트리 전체의 높이가 높아진다.
• 포인터 수보다 공간 활용도를 기준으로 Split이나 Merge가 이루어진다.
• Prefix Compression
  • 문자열의 크기를 줄이기 위해 internal 노드들에는 전체 문자열보다는 접두사를 키값으로 둘 수 있다.

Bulk Loading

• 하나씩 B+tree에 삽입하게 되면 매번 파일 I/O가 일어나게 되어 매우 비효율적이다. 만약, 리프 노드가 메모리에 올라올 수 없는 사이즈라도 한다면 더욱 비효율적이다.
• Solution 1 : 정렬해서 순서대로 삽입한다.
  • 이렇게 하면 비어있는 page에 순서대로 쌓이다가 Split이 일어나게 된다.
  • 그러면 매번 I/O를 매번할 필요가 없어지지만, 대부분의 노드가 절반만 차게 된다.
• Solution 2 : 상향식 B+Tree 구조
  • 마찬가지로 정렬을 한 후에 리프 노드단계부터 삽입해나가는 방식
  • 여러 데이터베이스 시스템에서 큰 데이터가 들어왔을 때 사용하는 방식이다.

Indexing on Flash

• 플래쉬 메모리(20-100ms)는 마그네틱(5-10ms)보다 훨씬 빠르다.
• 하지만, 쓰기가 랜덤으로 되기 때문에 결국 지우는 과정이 많이 든다.
• 그리고 디스크의 블록 사이즈보다 플래시의 페이지 사이즈가 작기때문에 노드 사이즈가 더 작아야 한다.
• 상향식 B+Tree구조를 사용하면, Erase하는 과정이 적어지지 때문에 성능이 확실히 향상된다.
• 외에도 여러 변형 B+tree구조가 지우는 과정을 줄이기 위해 나와있다.

Indexing in Main Memory

• 캐시 누락을 줄이기 위해서는 캐시에 맞는 작는 노드로 재분배하는게 중요하다. 그래야 Space overhead없이 사용할 수 있다.
• 큰 데이터베이스 전체를 메모리에 올리는 것은 불가능하므로, 노드 사이즈를 키워서 디스크 접근을 최소화하는 것은 좋지만, 캐시 누락을 위해서는 큰 노드 내에 캐시 사이즈에 맞는 작은 노드로 트리를 구성하는 게 단순 배열보다 좋다.