B+ 트리
From Wikipedia, the free encyclopedia
B+ 트리(Quaternary Tree라고도 알려져 있음)는 컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종이다.
이 문서의 내용은 출처가 분명하지 않습니다. (2014년 7월) |
이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(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+트리 타입을 가끔 사용한다.