B Tree & B+ Tree

2-3 Tree

• 이전 글에서 다뤘던 Binary Tree 와 Binary Search Tree 는 자식 노드를 최대 2개 밖에 갖지 못한다. 하지만 자식 노드를 3개 갖도록 한 Tree 가 2-3 tree 라고 부른다. 2-3 tree의 특징은 아래와 같다. 왜 2-3 tree 라고 부르냐면, degree (child node의 수)가 2 또는 3이기 때문이다. 즉, 최소 child 의 개수는 2개라는 의미이다. 2-3 Tree는 다음과 같은 특징을 갖는다.
  1. 하나의 노드는 최대 2개의 key (3개의 자식 노드)를 갖는다.
  2. 2-3 tree는 self-balancing tree 다.
  3. 모든 leaf node 는 같은 레벨을 갖는다.
  4. 모든 internal node는 항상 2개 이상의 자식 노드를 갖고 있어야 한다. 그렇지 않으면 자식 노드와 merge 가 되어 버린다.
  5. 2-4 이유 때문에 balance 가 깨지면 부모로부터 key 를 빌려오는 행위를 한다.

Insert

• 삽입은 다음과 같은 과정을 거친다.
  • 기본적으로 leaf node 까지 간 후 삽입하면서 rebalancing 을 진행한다.
  • 삽입을 할 때는 leaf node에서 부모로 타고 올라가는 방식을 취하는데, 이 방법을 상향식 이라고 한다.
  • [분할이 발생하지 않는 경우] 노드의 키가 1개 밖에 없으면, 그냥 키를 추가한다.
  • [분할이 발생하는 경우]) 노드의 키가 2개 있으면 (overflow), split 을 진행한다.
  • split 을 하는 과정은 3개의 키 중 중간 키를 부모로 올리고 왼쪽 그 부모의 오른쪽 왼쪽 자식 노드로 만든다. 이 말은 즉, 부모가 없는 경우 새로운 부모를 만들거나, 부모가 있는 경우 그 노드에 하나의 key 를 추가하고 왼쪽 오른쪽 자식 노드로 만든다.

• Insert 70을 하는 경우 overflow 가 발생했기 때문에 중간값이 60을 부모로 올린다. 그리고 60의 child 는 50, 70이 된다.
• 부모를 올렸을 때, 60은 20, 40, 60 이렇게 또 overflow 가 된다. 위와 같은 방법으로 40이 부모가 되고, 20, 60이 left, right child 가 된다.
• 그 결과 아래와 같이 된다.

Delete

• 삭제는 다음과 같은 과정을 거친다
  • 삭제는 자식 노드의 key 값으로 대체하고, 자식 노드를 업데이트하는 방식으로 진행되기 때문에 하향식이라고 불린다.
  • 삭제시키는 노드의 leaf node 인 경우
    • 나 최소보다 큼: 그냥 지운다
    • 나 최소보다 작고, 형제 최소보다 큼: 부모한테 빌리고, 형제는 부모에게 빌려준다.
    • 나 최소보다 작고, 형제, 최소보다 작고, 부모 최소보다 큼: 부모가 빌려주고, 형제랑 merge 한다
    • 나, 형제, 부모 모두 최소: 트리의 재구조화를 통한 높이 조절 발생. merge 한 후 internal node 삭제 로직으로 처리한다.
  • 삭제시키는 노드가 internal node 인 경우
    • 용어: 왼쪽 child 에서는 가장 큰 노드를 (inorder predecessor), 오른쪽 child 에서는 가장 작은 노드 (inorder successor)
    • 나 최소보다 크거나, 내 자식이 최소보다 큼: 현재 노드의 inorder predecessor 또는 inorder success 를 가져와서 replace 함
    • 나, 내 자식 모두 최소: 트리의 재구조화를 통한 높이 조절 발생. 자식들은 merge 를 진행. 키를 지우면 부모랑 형제를 merge 함. 자식 노드를 삭제된 키의 병합된 자식 노드로 설정. 이 때, 삭제된 키의 부모 노드의 개수에 따라 또 다르게 대응한다.
      • 1. 키의 부모와 형제가 병합되면서 overflow 가 발생하면 분할을 진행.
      • 2. 키의 부모가 최소 키의 개수가 안되는 경우가 발생하면 그 부모 (조부모) 를 따라가서 동일한 로직으로 부모와 형제를 병합시킴.

• Delete 90을 하면 80을 내리고 (70, 80) 이 하나의 노드가 된다.
  

• Delete 70을 하면, 60이 아래로 내려오고, 이 때, 60 자리는 다시 underflow가 됐기 때문에 부모로 부터 빌려온다. 이 때, 빌려온 부모가 Root 이고, 이 Root 가 비었으므로, (20, 40) 이 하나의 노드가 되고 최종 결과는 아래와 같이 된다.
  

위 시뮬레이션은 leaf node 만 해당되었는데, 사실 leaf node 보다 internal node를 처리하는게 로직이 더 복잡하다. 설명은 다음 링크에 잘 나와있으니까 까먹으면 매번 다시 업데이트를 하자. https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Tree

simulator:
https://people.ksp.sk/~kuko/gnarley-trees/23tree.html

B Tree

• B Tree는 2-3 tree의 확장된 Tree로 child node 의 개수가 M개 이다. 여기서 M을 degree 라고 부른다.
• B Tree의 장점에는 여러가지가 있는데, 먼저 Binary Search Tree의 height를 낮출 수 있다. Tree 의 height 를 낮춰야 하는 이유가 있을까? 매우 큰 크기의 데이터를 저장할 때 Disk 에 저장을 하는 경우가 있다. 따라서 노드의 크기를 Disk의 Block size 로 한 후 block 을 메모리에 로드해서 탐색을 한 후, 데이터를 찾지 못한 경우 다시 disk 에서 불러오도록 한다. height 가 disk access 횟수라고 했을 때, B Tree 구조는 disk access 횟수를 줄일 수 있는 자료구조이다.
• 또다른 장점으로는 데이터가 정렬된 상태로 저장되어있다는 것이다. 하나의 노드 (또는 블록)안에 저장된 데이터는 정렬된 상태로 저장하기 때문이다.
• B Tree 의 조건은 2-3 Tree 와 상당 부분 같다. 다만, 2개의 key, 3개의 child라는 조건이 M-1개의 key, M개의 child 라는 조건으로 변경되었다는 것 뿐이다.
• 여기서 underflow 와 overflow 조건이 중요해지는데, overflow 의 조건은 노드가 가질 수 있는 max key 개수인 M-1개가 꽉찰 경우 overflow 라고 판단한다.
• underflow 인 경우는 노드가 가지는 child 의 개수가
  $ceiling(M/2)$ 인 경우이다. 즉, 2-3 Tree의 경우
  $M=3$ 이기 때문에 최소로 가져야 하는 child의 개수는
  $ceiling(3/2)=2$ 이다. 따라서 child 의 개수가 2가 안되는 경우에는 child 와 merge 해버리는 상황이 발생한다.

B+ Tree

• B+ Tree 는 Database의 index를 구성할 때 많이 사용된다. B+ Tree가 B Tree 보다 가지는 이점은, leaf node에만 데이터가 저장되기 때문에 메모리 공간을 적게 사용한다는 것이다. 따라서 하나의 노드에 더 많은 키를 저장할 수 있다는 장점이 있다. 이게 무슨 말인가 하면, B Tree 에서는 노드에 데이터도 포함될 수 있지만, B+ Tree의 경우에는 노드에 데이터가 포함될 수 없다. 대신 B+ Tree는 block pointer를 갖고 있다 .
• 또한 Full scan 을 하는 경우 B Tree의 경우 모든 노드를 방문해야하는 반면, B+ Tree의 경우 linear 하게 leaf 노드들만 방문하면 되기 때문에 속도가 더 빠르다고 한다. leaf 노드들은 서로 Linked List로 연결되어 있기 때문에 Tree를 탐색할 필요없이 Linked List처럼 탐색할 수 있고, 이로 인해 Range Query 에서도 유용하게 쓰일 수 있다.
• B+ Tree의 단점이라고 하면, Worst case, Best case 모두 O(h) 라는 것이다. B Tree 의 경우 빠르면 O(1) 에도 찾을 수 있는 반면, B+ Tree는 데이터가 항상 leaf node 에 있기 때문에 항상 O(h)이다. 여기서 h는 height를 의미한다.

DB Index 와 B Tree & B+Tree

• Index 는 DB 의 Full Scan 을 방지하고 빠르고 적은 시스템 부하로 데이터를 찾을 수 있게 함. Index 의 장점은 데이터를 정렬해놓기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있음.
• DB 에 Index를 사용하면 좋은 경우와 좋지 않은 경우
  • 좋은 경우
    • 테이블의 규모가 큰 경우
    • 컬럼에 insert, update, delete 가 자주 발생하지 않은 경우
    • Where 나 order by, join 등이 자주 사용되는 컬럼
    • 데이터의 중복도가 낮은 컬럼
  • 나쁜 경우
    • 컬럼에 insert, update, delete 가 자주 발생하는 경우
    • 데이터의 10~15% 이상의 많은 양의 데이터를 처리하는 경우
    • Range 가 적은 컬럼
• Index 를 구현하는 두 가지 방법
  • Hash table
    • best case 인 경우, 중간노드에서 데이터를 찾으면 검색 속도가 빠르다.
    • 등호 연산 처리는 빠르지만, range query 에는 빠른 시간 내 처리가 어려움. 따라서 잘 사용하지 않음.
    • 모든 데이터를 순회하는데 트리의 모든 노드를 방문해야하므로 비효율적 (재방문이 있음).
  • B+ Tree
    • B+는 오직 데이터를 leaf 노드에만 저장하고, leaf 노드는 linked list 로 연결되어 있기 때문에 range query 방식에 유리함.
    • Leaf 노드말고 중간 노드에서는 데이터를 담아두지 않기 때문에 메모리를 더 확보해서 더 많은 key 를 저장할 수 있음. 이는 cache hit 을 높일 수 있다는 말임.