[자료구조] B tree & B+ tree

B tree

이진트리는 검색을 위한 자료구조로 하나의 부모가 두 개의 자식밖에 가지질 못하고 자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지지만 잠재력이 가장 크다. 

구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제가 O(logN)의 성능을 보이는 장점이 있다.

 

이를 보완하고자 나온 것이 B tree이다.

B tree는 하나의 노드에 여러자료가 배치되는 트리 구조이다. 

한 노드에 M개의 자료가 배치되면 M차 B-Tree라고 한다. 즉, 5차 B-Tree인 경우 자식노드가 최대 5개인 것이다. 

최악의 경우  O(logN)의 검색 성능을 보이지만, 하나의 노드에 많은 데이터를 저장할 수 있는 것이 이진트리와 다른 장점이다.

 

 

 

특징

• 더 많은 자식을 가질 수 있다.
  • 이진트리를 확장하여 더 많은 자식을 가질 수 있도록 일반화하였다.
  • 덕분에 트리의 높이를 낮출 수 있다. 
• 트리의 균형을 자동으로 맞추는 로직을 갖추고 있다.
  • 균형 로직은 단순하면서 효율적이다. 
  • B-tree는 레벨로 따졌을 때 완전히 균형을 맞춘 트리이다.
• 하나의 노드에 많은 데이터를 가질 수 있다.
  • 대량의 데이터를 처리해야 하는 검색 구조인 경우에 유리하다.
  • 대량의 데이터는 메모리 보다는 하드디스크 / SSD에 저장되어야 하는데 이러한 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문이다.
  • 한 블럭이 1024 바이트라면 2바이트를 읽으나 1024 바이트를 읽으나 입출력에 대한 비용은 동일하다. 그렇다면 하나의 노드를 1024바이트가 되도록 조절하여 입출력 측면에서 효율적인 구성이다.
  • 데이터베이스 시스템의 인덱스 저장 방법으로 많이 쓰인다.

 

규칙

• 노드의 자료수가 N이라면 자식의 수는 N+1이어야 한다.
• 각 노드의 자료는 정렬된 상태여야 한다.
• 노드의 자료Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고 오른쪽 서브트리는 Dk보다 큰 값들이어야 한다.
• Root 노드는 적어도 2개 이상의 자식을 가져야 한다.
• Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
• 외부 노드로 가는 경로의 길이는 모두 같다.
  • 외부노드는 모두 같은 레벨에 있다
• 입력자료는 중복될 수 없다.

 

 

B* Tree

B-Tree는 적은 수의 노드를 생성하는 것이 인덱스 구조의 성능을 높일 수 있다.

생성되는 노드의 수를 줄이기 위해 B-Tree의 변형으로 B* 트리가 나오게 되었다.

 

B-tree는 B-tree의 특성을 유지하기 위해 삽입과정에서의 분열과 삭제 과정에서의 합병 등의 보조 연산이 필요하다.

B* Tree에서는 이런 보조 연산을 가급적 지연시켜 회수를 감소시키려 한다.

 

 

특징

• 노드의 분열을 줄여서 보조 연산을 줄이려고 한다.
  • 노드가 가득차면 분열하는 대신 가까운 형제 노드로 재배치 한다.
  • 인접 노드까지 모두 가득찰 때까지 분열을 지연한다.
  • 인접 노드에도 overflow가 일어나서 더 이상 빈 자리가 없을 경우, 가득찬 두 노드를 분열하여 2/3 정도 채워진 3개의 노드로 만든다.
    • 재배치 동작은 2번 발생한다. 
• 모든 노드는 2/3 이상 채워져야 된다. (Root 노드 제외)
  • B-tree는 1/2 이상
• 삭제 시 key 값의 개수가 모자라면 이웃한 형제 노드로부터 재배치하고 재배치도 할 수 없는 경우 합병한다.
  • 세 개의 노드를 두 개의 노드로 합병한다.

 

B+ tree

B-tree의 순회 작업이 복잡하였지만 B+ tree가 문제점을 해결하였다. 

인덱스 구조에서 순차접근에 대한 문제의 해결책으로 제시되었다. 

B-트리에서는 특정 key 값이 하나의 노드에서만 존재할 수 있지만, B+ tree에서는 leaf 노드와 leaf의 부모 노드에서 공존할 수 있다. 

 

특징

•  index 부분과 leaf 노드로 구성된 순차 data 부분으로 이루어진다. 
•  Index 부분의 key 값은 leaf에 있는 key 값을 직접 찾아 가는데 사용하고 모든 key 값은 leaf 노드에 나열된다. 
  •  index 부분의 key 값도 leaf 노드에 다시 한 번 나열된다.
• Leaf 노드는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.
• 노드의 분열이 일어나면 중간 key 값이 부모 노드로 올라간다.
  • 이는 새로 분열된 노드에도 포함되어야 한다.
• 새 노드는 leaf 노드끼리의 linked list에도 삽입되어야 한다.
• 재배치와 합병이 필요하지 않을 때는 leaf 노드에서만 삭제된다.
• leaf node의 값이 삭제되어도 삭제하지 않는다.
  • 다른 key 값을 찾는데 사용될 수 있기 때문
• 재배치할 경우 노드의 key 값은 변하지만 tree 구조는 변하지 않는다.
• 합병을 할 경우 index 부분에서도 key 값을 삭제한다.

 

 

B tree & B+ tree

 

공통점

• 모든 leaf의 깊이(depth)는 같다.
• 각 node에는 k/2 ~ k 개의 item이 들어있다.
• 검색(순회)가 비슷하낟.
• 삽입 시 overflow가 발생하면 분열한다.
• 삭제 시 underflow가 발생하면 재배치하거나 합병한다.

 

차이점

노드의 Key와 데이터

• B-tree: 각 노드에 key값 + 데이터도 들어간다.
  • 데이터는 디스크 블럭으로부터 포인터가 될 수 있다.
• B+ tree: 각 노드에 key값만 들어가야 한다.
  • 데이터는 오직 leaf에만 존재한다.

 

add, delete

• B+ tree: add, delete가 leaf에서만 이루어진다.

 

 linked list

• B+ tree: leaf 노드끼리 linked list로 연결되어 있다.
  • 연속적인 범위 탐색에 매우 유리하다.