가장 먼저 도입된 알고리즘이자, 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다. B-Tree에도 여러 변형된 알고리즘이 있다. 일반적으로 DBMS에서는 B+-Tree, 또는 B*-Tree가 사용된다. 참고로 B-Tree에서 B는 Balanced를 의미한다.
B-Tree는 트리 구조의 최상위에 하나의 루트노드가 존재하고, 그 하위에 자식 노드가 붙어 있는 형태이다. 트리 구조의 가장 하위 노드를 리프라고 하고, 루트도 리프도 아닌 중간 노드들을 브랜치라고 한다.
트리 안에서 루트와 브랜치는 자식 노드 주소를 갖고 있지만, 리프는 실제 데이터 레코드를 찾아가기 위한 주솟값을 갖고 있다. 이를테면 이런 관계이다.
보통 RDMBS에서 데이터 레코드는INSERT된 순서로 저장된다고 알려져있다. INSERT만 했다면 맞을 수 있다. 하지만 만약 DELETE가 일어나면 다음 INSERT는 이 빈공간에 일어난다. 따라서 항상 INSERT된 순서로 저장되어있지 않다.
MySQL InnoDB 테이블에서 레코드는 클러스터링되어 디스크에 저장된다. 따라서 기본적으로 프라이머리 키 순서로 정렬되어 저장된다. 여기서 클러스터링이란, 비슷한 값을 최대한 모아서 저장하는 방식을 의미한다. 오라클의 IOT(Index organized table)이나 MS-SQL의 클러스터 테이블도 모두 같은 구조를 의미한다.
다른 DBMS에서는 이 클러스터링이 선택사항이지만 InnoDB에서는 기본값이 클러스터링 테이블이다. 따라서 MySQL에선 PK키 순서로 정렬되어 저장된다.
다시 인덱스로 돌아가겠다. 인덱스는 테이블의 키 컬럼만 갖고 잇으므로 나머지 전체 행을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 리프가 레코드의 주소들을 갖고 있다. 리프 노드는 인덱스키:레코드 주소의 키-값 레코드를 나열한 페이지이다.
아래는 InnoDB에서 인덱스와 PK간의 관계를 나타내는 그림이다. InnoDB 테이블은 PK를 주소처럼 사용하기 때문에 인덱스가 논리적인 주소(PK)를 갖는다고 할 수 있다.
반면 MyISAM 엔진에서 인덱스가 갖는 레코드 주소는, 데이터 파일내 위치(OffSet)이거나 테이블에 Insert된 순번이다.
출처: RealMySQL 8.0, 222p, 그림 8.6
따라서 InnoDB에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 못한다. 위 그림에서처럼 인덱스에 저장되어있는 PK를 한번 찾아간 후, PK 인덱스의 리프 페이지에 저장된 레코드를 찾아간다.
즉, InnoDB에서는 모든 보조키 인덱스검색에서 레코드를 읽기위해선 PK를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다. 이로인한 장단점은 8.8에서 다룰 것임.
새로운 키 값이 B-Tree에 저장될 때, 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. B-Tree에 저장될때는 B-Tree내에서 새로운 데이터가 저장될 적절할 위치를 결정해야 하고, 그리고 나서 대상 레코드의 주소 정보와 레코드의 키를 B-Tree의 리프에 새로 저장한다. 만약 리프페이지가 꽉 차서 더 저장할 수 없다면, 리프 노드가 분리(Split)되어야 한다. 이러면 상위 브랜치 노드가 처리해야할 범위가 넓어진다. 이 탓에 B-Tree는 쓰기 작업에 비용이 많이 드는 것으로 알려져있다.