B-tree

대부분의 DB 인덱스가 속에 쓰는 나무 모양의 자료 구조다. 값을 크기 순서대로 가지를 타고 내려가며 찾기 때문에 데이터가 아무리 많아도 비교 몇 번 만에 원하는 값 근처에 도달한다. 전화번호부를 반으로, 또 반으로 쪼개며 찾아가는 방식과 비슷하다.