B+ 트리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
단순한 B+ 트리의 예

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

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

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

B+트리에서 중요한 가치는 블록-지향적인 storage context 에서 효율적인 검색을 위해 데이터를 저장하는 것이다. b 크기의 a개 블록을 가진 주어진 저장 시스템, a * b 만큼의 키들을 저장하는 B+ 트리는 바이너리 서치 트리( 비블록지향적인 데이터 구조 contexts )와 비교할 때 매우 효율적일 것이다.

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

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

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

관련 항목[편집]