B+ 트리

B+ 트리(Quaternary Tree라고도 알려져 있음)는 컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종이다.

이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성된다.

B트리와 대조적으로 B+트리는, 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. 오직 키들만이 내부 블록에 저장된다.

B+트리에서 중요한 가치는 블록-지향적인 storage context(예: filesystem)에서 검색을 효율적으로 할 수 있다는 점이다. 바이너리 서치 트리에 비해 B+트리 노드의 fanout(한 노드의 자식 노드의 수)이 훨씬 높아서 검색에 필요한 I/O 동작 회수를 줄일 수 있기 때문이다.

ReiserFS filesystem (Unix and Linux)
XFS filesystem (IRIX, Linux)
JFS2 filesystem (AIX, OS/2, Linux)
NTFS filesystem (Microsoft Windows)

위의 파일시스템들은 모두 블록 인덱싱을 위해 B+트리 타입을 사용한다.

관계 데이터베이스들도 테이블 인덱스를 위해 B+트리 타입을 가끔 사용한다.

알고리즘

검색

B+ 트리의 루트는 트리내에 존재하는 값들의 범위를 나타낸다, 즉 모든 내부노드들은 하위 범위이다.

B+ 트리의 값 k를 찾아보자. 루트로부터 시작해서 k를 포함하는 단말노드를 찾아보려고한다. 각 노드마다 어떤 포인터를 따라갈지 알아내야한다.

Function: search (k)
  return tree_search (k, root);

Function: tree_search (k, node)
  if node is a leaf then
    return node;
  switch k do
  case k < k_0
    return tree_search(k, p_0);
  case k_i ≤ k < k_{i+1}
    return tree_search(k, p_{i+1});
  case k_d ≤ k
    return tree_search(k, p_{d+1});

이 수도코드는 동일한 키가 존재하지 않는다고 가정한다.

접두사 키 압축

팬아웃(fan-out)을 늘리는 것이 중요하다. 이유는 단말노드의 검색을 더욱 효율적으로 만들기 때문이다.
인덱스 엔트리들은 압축이 가능하다.

삽입

먼저 검색을 실시함으로써 어떤 버킷(공간)에 새로운 레코드를 넣을지를 결정한다.

만약 버킷이 꽉차있지 않다면(삽입후 최대 b-1개의 엔트리), 레코드를 추가한다.
버킷이 꽉차있다면, 버킷을 쪼갠다.
- 새로운 단말노드의 메모리를 확보하고, 버킷에 든 구성요소의 절반을 새로운 노드로 옮긴다.
- 새 단말노드의 최소 키를 부모에게 삽입한다.
- 만약 부모가 꽉찼다면, 부모 역시 쪼개도록 한다.
  - 부모노드에게 중간키를 추가한다.
- 쪼개지지 않는 부모를 발견할 때까지 이를 반복한다.
루트가 쪼개졌다면, 새로운 루트를 만드는데 이 루트는 1개의 키와 2개의 포인터를 지녀야 한다.(즉, 새 루트로 올라간 값은 기존 노드에서 사라진다.)

삭제

루트에서 시작하여, 엔트리가 속한 단말노드 L을 찾는다.

엔트리를 삭제한다.

L이 절반이상 차있다면 종료한다.
L이 절반 이하라면,
- 형제(L과 동일한 부모를 가진 인접노드)가 절반 초과라면, 재분배하고 엔트리를 빌려온다.
- 형제의 엔트리들이 정확히 절반일경우에는 L과 형제를 병합한다.
병합이 일어났다면, L의 부모로부터 삭제된 노드를 가리키는 포인터를 삭제한다.
병합은 루트까지 전파되어, 트리의 높이를 감소시킬 가능성이 있다.

벌크-로딩

데이터 모음을 이용하여 열(field)에 대한 B+ 트리 인덱스를 생성하고자 한다. 한가지 방법은, 레코드를 빈 트리에 삽입하는 것이다. 하지만, 이는 비용이 많이드는데 그 이유는 각 엔트리들을 루트노드부터 시작하여 올바른 곳으로 위치시켜야 하기 때문이다. 대안책으로는 벌크-로딩(bulk-loading)이다.

첫번째 단계는 데이터 엔트리들을 검색 키에 대하여 오름차순으로 정리하는 것이다.
이제 빈페이지를 위한 공간을 확보하고, 루트를 만든다. 이후, 첫페이지를 가리키는 포인터를 삽입한다.
루트가 꽉차면, 루트를 쪼개고 새로운 루트 페이지를 만든다.
엔트리 삽입을 계속하고 가장 오른쪽에 존재하는 인덱스페이지가 단말레벨 위에 올때, 모든 엔트리가 인덱스 되었을시에 멈춘다.

구현

B+ 트리의 단말노드는 대체로 연결리스트 구조로 서로 연결되어있다. 이는 블록에 대한 범위 쿼리를 더욱 효율적으로 만든다. 덧붙여서, 이는 공간소모가 심하지 않고, 트리의 유지에 복잡성을 더하지 않는다. 이는 B+트리가 B-보다 훨씬 장점이 있음을 보여준다. B-트리에서, 모든 키가 단말에 존재하지 않기 때문에, B+트리와 같은 정렬된 연결리스트는 존재하지 않는다. 그러므로 B+트리는 데이터베이스 시스템 인덱스구성에서 매우 효율적인데, 디스크상에 존재하는 데이터들을 위한 효율적인 자료구조를 제공하기 때문이다.

어떠한 저장 시스템이 B바이트의 블록사이즈를 지니고, k사이즈에 키들이 존재한다고 가정하자. 이때 가장 효율적인 B+트리는 b = (B/k)-1이다. 이론상 1비트를 빼주는 건 불필요하지만 실제로는 인덱스블록에 추가공간이 존재한다. 인덱스블록이 실제 블록보다 약간이라도 크다면 이는 성능하락을 가져오므로 이를 처리하는게 바람직하다.

B+트리의 노드들이 배열로 이루어져있다면, 삽입 혹은 삭제시 반정도의 값들을 움직여야하므로 상당히 느리다. 이를 극복하기 위하여 노드에 존재하는 구성요소들을 이진트리 혹은 B+트리로 구성하도록 한다.

B+ 트리는 램 내부에 존재하는 데이터에도 사용된다. 이 경우, 합리적인 블록 사이즈는 프로세서 캐시라인의 사이즈가 된다.

같이 보기

B 트리