B+트리

B-트리를 고친 모양이다. 위쪽 노드에는 길 안내용 키만 두고, 실제 데이터는 맨 아래 잎(leaf) 노드에만 둔다. 잎 노드끼리는 옆으로 줄줄이 이어 두는 경우가 많아서 「10부터 20까지」 같은 범위를 차례로 읽기 쉽다. 한 노드에 키를 보통 100개 넘게 담아 트리가 납작해지므로, 값을 찾을 때 디스크를 읽는 횟수가 줄어든다. 그래서 파일 시스템처럼 디스크에 블록 단위로 담는 곳에 쓴다.