B-트리는 삽입과 삭제의 선형 비용 문제를 해결하는 다단계 인덱스이다. 이것이 B-트리가 좋은 이유이고, 인덱스를 표현하는 표준 방법이 된 이유이다. 해결 방법은 두 부분으로 나뉜다. 첫 번째는 가득 차게 될 인덱스 레코드를 요구하지 않는다. 두 번째는 다음 레코드로 오버플로우(overflow) 키를 넘기지 않는다. 대신 초과되는 레코드를 두개의 인덱스 레코드로 각각 반씩 나눈다. 삭제는 필요할 때 인덱스를 하나의 레코드로 합치는 전략을 취한다.
B-트리의 각각의 노드는 인덱스 레코드이다. 이 레코드의 각각은 B-트리의 차수(order)라고 불리는 키-참조 쌍의 최대수를 가질 수 있다. 또한 보통 차수의 반인 최소소의 키-참조 쌍을 가질 수 있다. 차수가 100인 B-트리는 레코드 당 최소 50개의 키와 최대 100개의 키를 가질 수 있다. 유일한 예외는 하나의 루트 노드이고, 이것은 두 개의 키만을 가질 수도 있다.
가득 차지 않은 인덱스 레코드에 새로운 키를 삽입하는 비용은 적다. 단지 인덱스 레코드를 갱신하면 된다. 만약 삽입되는 키가 인덱스 레코드에서 새로운 가장 큰 키이면, 그 레코드의 더 높은 레벨의 새로운 키가 되고, 키가 삽입된 더 높은 레벨의 레코드를 갱신해야 한다. 비용은 트리의 높이에 의해 제한된다.
인덱스 레코드에 레코드 크기 초과가 발생하면, 이 인덱스 레코드는 2개의 레코드로 분할되며, 각각 키의 반을 가지게 된다. 새로운 인덱스 노드가 이 레벨에서 생성되었기 때문에, 이 새로운 노드의 가장 큰 키가 다음 더 높은 레벨의 노드에 삽입되어야 한다. 이것을 키의 상승(promotion)이라 한다. 키의 상승은 해당 레벨에서 오버플로우(overflow)를 발생시킬 수 있으며, 이 오버플로우가 트리의 성장을 의미한다. 또, 다음 레벨에서의 키의 삽입 역시 오버플로우를 발생시킬 수 있기 때문에, 결과적으로 삽입 비용은 트리의 높이에 의해 제한된다. 삽입에 의해서 영향을 받는 노드는 레벨 당 2개 이하이며, 따라서 삽입 비용은 트리 높이에 선형적이다. 그러나 삽입은 간단하게 이뤄지는데 비해, 삭제는 여러가지 상황을 야기할 수 있기 때문에 복잡하다.
Reference
MIcheal J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addison Wesley
Library/File Structure