Loading AI tools
위키백과, 무료 백과사전
B+ 트리(Quaternary Tree라고도 알려져 있음)는 컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종이다.
이 문서의 내용은 출처가 분명하지 않습니다. (2014년 7월) |
이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성된다.
B트리와 대조적으로 B+트리는, 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. 오직 키들만이 내부 블록에 저장된다.
B+트리에서 중요한 가치는 블록-지향적인 storage context(예: filesystem)에서 검색을 효율적으로 할 수 있다는 점이다. 바이너리 서치 트리에 비해 B+트리 노드의 fanout(한 노드의 자식 노드의 수)이 훨씬 높아서 검색에 필요한 I/O 동작 회수를 줄일 수 있기 때문이다.
위의 파일시스템들은 모두 블록 인덱싱을 위해 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});
이 수도코드는 동일한 키가 존재하지 않는다고 가정한다.
먼저 검색을 실시함으로써 어떤 버킷(공간)에 새로운 레코드를 넣을지를 결정한다.
엔트리를 삭제한다.
데이터 모음을 이용하여 열(field)에 대한 B+ 트리 인덱스를 생성하고자 한다. 한가지 방법은, 레코드를 빈 트리에 삽입하는 것이다. 하지만, 이는 비용이 많이드는데 그 이유는 각 엔트리들을 루트노드부터 시작하여 올바른 곳으로 위치시켜야 하기 때문이다. 대안책으로는 벌크-로딩(bulk-loading)이다.
B+ 트리의 단말노드는 대체로 연결리스트 구조로 서로 연결되어있다. 이는 블록에 대한 범위 쿼리를 더욱 효율적으로 만든다. 덧붙여서, 이는 공간소모가 심하지 않고, 트리의 유지에 복잡성을 더하지 않는다. 이는 B+트리가 B-보다 훨씬 장점이 있음을 보여준다. B-트리에서, 모든 키가 단말에 존재하지 않기 때문에, B+트리와 같은 정렬된 연결리스트는 존재하지 않는다. 그러므로 B+트리는 데이터베이스 시스템 인덱스구성에서 매우 효율적인데, 디스크상에 존재하는 데이터들을 위한 효율적인 자료구조를 제공하기 때문이다.
어떠한 저장 시스템이 B바이트의 블록사이즈를 지니고, k사이즈에 키들이 존재한다고 가정하자. 이때 가장 효율적인 B+트리는 b = (B/k)-1이다. 이론상 1비트를 빼주는 건 불필요하지만 실제로는 인덱스블록에 추가공간이 존재한다. 인덱스블록이 실제 블록보다 약간이라도 크다면 이는 성능하락을 가져오므로 이를 처리하는게 바람직하다.
B+트리의 노드들이 배열로 이루어져있다면, 삽입 혹은 삭제시 반정도의 값들을 움직여야하므로 상당히 느리다. 이를 극복하기 위하여 노드에 존재하는 구성요소들을 이진트리 혹은 B+트리로 구성하도록 한다.
B+ 트리는 램 내부에 존재하는 데이터에도 사용된다. 이 경우, 합리적인 블록 사이즈는 프로세서 캐시라인의 사이즈가 된다.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.