지금까지 다룬 자료 구조는 모두 메인 메모리에 상주합니다. 그러므로 자료 구조 성능을 평가할 때 빅오만으로도 비교가 가능했습니다. 그런데 조금만 더 생각해 보면 많은 데이터가 데이터베이스에 있습니다. 데이터베이스는 보조 기억 장치에 데이터를 저장하죠. 데이터를 보조 기억 장치에 저장한다면 이야기는 달라집니다. 지금까지 공부했던 자료 구조를 보조 기억 장치에서 사용한다면 빅오는 의미가 없어집니다. 데이터를 메인 메모리로 읽어 오거나 보조 기억 장치에 쓰는 연산이 함수 대부분의 실행 시간을 차지할 것이기 때문이죠. 그렇다면 지금까지 공부한 자료 구조는 오로지 메인 메모리에 상주하는 데이터를 다루기 위한 것일까요? 그렇지 않습니다. 자료 구조를 하드웨어 특성과 잘 맞물려 조금 변형한다면 보조 기억 장치로 삽입, 탐색, 삭제할 때 성능을 좀 더 좋게 할 수 있습니다.

이 장에서 알아볼 B 트리는 많은 데이터베이스 시스템에서 데이터를 저장하고 다루는 데 사용하는 매우 중요한 자료 구조입니다. 먼저 메모리 계층 구조부터 시작합시다.