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

단순한 B+ 트리의 예

이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(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+ 트리는 램 내부에 존재하는 데이터에도 사용된다. 이 경우, 합리적인 블록 사이즈는 프로세서 캐시라인의 사이즈가 된다.

같이 보기

편집