가변 길이 레코드 집합을 탐색하기 위해 인덱스(index)를 사용하는 것은 효과적인 기법이다. 그러나, 문제는 인덱스 전체를 메모리에 올릴 수 없는 경우이다. 이 문제를 해결하기 위해, 1972년 Bayer와 McCreight가 발표한 논문의 처음 몇 단락을 보기로 하자. 여기에서는 그들이 B-트리(B-Tree)로서 해결하고자 했던 문제, 즉 메모리로 적재하기에는 너무 큰 인덱스의 접근과 유지에 관한 방법에 대해 간결하게 설명하고 있다.
여기서의 B-트리는 흔히 알려진 이진 트리를 의미하는 것이 아니다. 그렇다면, B-Tree에서 B가 뜻하는 것은 무엇인가? 이 의문에 대해, Comer(1979)가 남긴 주석을 살펴보면 다음과 같다.
보조 기억장치에 인덱스를 저장할 때 생기는 근본적인 문제는 보조 기억장치가 매우 느리다는 사실이다. 이 문제는 다시 두 가지 세부적인 문제로 분류할 수 있다.
1. 인덱스를 검색하는 것이 이진 탐색보다 빨라야 한다 : 디스크에서 키를 찾는 것은 종종 다른 디스크 트랙의 탐색을 야기한다. 탐색은 많은 비용이 요구되는 것이며, 키를 찾기 전에 서너군데 이상의 다른 장소를 뒤져야 한다는 것은 무척이나 많은 시간을 요구하는 것이다. 만약 이진 탐색 방법을 사용한다면 15개의 항목에서는 4회, 1000개의 항목에서는 평균 9.5회의 탐색이 필요하다. 따라서 좀 더 적은 검색으로 키에 접근할 수 있는 방법이 필요하다.
2. 삽입과 삭제는 검색만큼 빨라야 한다 : 하나의 키를 인덱스에 삽입하는 것이 인덱스의 다른 모든 키들의 이동을 초래한다면, 수천 개, 혹은 단지 수백 개의 키로 구성된 인덱스를 보조 기억장치로 관리한다는 것은 매우 비실용적일 것이다. 우리는 인덱스의 전체적 재구성이 아니라 부분적인 변화만을 줄 수 있는 키의 삽입과 삭제에 대한 방법을 연구해야 한다.
이것이 바로 1970년에 Bayer와 McCreight가 직면했던 문제이다. 그들은 보조 기억장치의 검색을 위해 다단계 인덱스와 트리 구조를 사용하도록 하는데 선구적인 역할을 담당했다.
Reference
Micheal J. Folk, Bill Zoellick, Gerg Riccardi, File Structure, Addison Wesley
....
이 논문에서는 동적으로 변화하는 임의 접근 파일(random access file)을 위해서 인덱스를 구성하고 유지하는 문제에 관해 고찰한다. 여기서 인덱스라 함은 물리적으로 인접한 고정된 크기의 두 데이터 항목, 즉 키(key) x와 관련 정보 a가 갈협하여 한 쌍을 이룬 (x, a) 인덱스 요소들의 집합을 의미하는 것이다. 키 x는 인덱스 내에서의 유일한 요소를 구별하고, 관련 정보 a는 임의 접근 파일 내의 레코드를 지시한다. 그러나 이 논문에서 다루고자 하는 문제는 관련 정보에 관한 것이 아님을 밝혀 둔다.
우리는 인덱스 자체의 용량이 너무 커서 주 기억 장치(primary storage)에는 일부분만이 저장되고 나머지 대부분은 백업 매체에 저장된다고 가정한다. 고려되는 백업 매체의 클래스는 의사 임의 접근 장치(pseudo random access device)인데, 이것은 긴 접근이나 지연 시간 - 코어 저장 장소와 같은 진짜 임의 접근과 비교할 때 - 을 가지며 물리적 순차 데이터의 전송이 일단 시작되면 높은 데이터 전송률을 가진다. 전형적인 의사 임의 접근 장치는 고정된 이동 헤드 디스크나 드럼(drum), 또는 데이터 셀(cell)이다.
데이터 파일 자체가 변경되기 때문에, 인덱스를 검색하고 원소를 검색하는 것 뿐만 아니라 키 - 실제적으로는 인덱스 원소 - 를 삭제하고 삽입하는 것도 경제적으로 할 수 있다. I를 인덱스의 크기로 하고 k는 페이지 크기를 나타내는 장치 의존적인 자연수라고 할 때, 이 논문에서 기술된 인덱스 구성은 키의 검색, 삽입, 삭제를 log2(I)에 비례하는 시간에 수행할 수 있다. 이 때 유지와 검색 방법의 성능이 거의 최적의 성능이 되게 한다.
....
여기서의 B-트리는 흔히 알려진 이진 트리를 의미하는 것이 아니다. 그렇다면, B-Tree에서 B가 뜻하는 것은 무엇인가? 이 의문에 대해, Comer(1979)가 남긴 주석을 살펴보면 다음과 같다.
....
B-트리의 기원에 관해서는 Bayer와 McCreight 그 누구도 설명한 적이 없다. 몇몇 사람들은 B가 Balanced, Broad, 또는 Bushy라고도 하고, 혹은 그들이 보잉(Boeing)사에서 일했다는 사실에서 B가 Boeing을 나타낸다고 주장한다. 그러나 B-트리의 B는 Bayer로 간주하는 것이 타당하다고 생각된다.
....
보조 기억장치에 인덱스를 저장할 때 생기는 근본적인 문제는 보조 기억장치가 매우 느리다는 사실이다. 이 문제는 다시 두 가지 세부적인 문제로 분류할 수 있다.
1. 인덱스를 검색하는 것이 이진 탐색보다 빨라야 한다 : 디스크에서 키를 찾는 것은 종종 다른 디스크 트랙의 탐색을 야기한다. 탐색은 많은 비용이 요구되는 것이며, 키를 찾기 전에 서너군데 이상의 다른 장소를 뒤져야 한다는 것은 무척이나 많은 시간을 요구하는 것이다. 만약 이진 탐색 방법을 사용한다면 15개의 항목에서는 4회, 1000개의 항목에서는 평균 9.5회의 탐색이 필요하다. 따라서 좀 더 적은 검색으로 키에 접근할 수 있는 방법이 필요하다.
2. 삽입과 삭제는 검색만큼 빨라야 한다 : 하나의 키를 인덱스에 삽입하는 것이 인덱스의 다른 모든 키들의 이동을 초래한다면, 수천 개, 혹은 단지 수백 개의 키로 구성된 인덱스를 보조 기억장치로 관리한다는 것은 매우 비실용적일 것이다. 우리는 인덱스의 전체적 재구성이 아니라 부분적인 변화만을 줄 수 있는 키의 삽입과 삭제에 대한 방법을 연구해야 한다.
이것이 바로 1970년에 Bayer와 McCreight가 직면했던 문제이다. 그들은 보조 기억장치의 검색을 위해 다단계 인덱스와 트리 구조를 사용하도록 하는데 선구적인 역할을 담당했다.
Reference
Micheal J. Folk, Bill Zoellick, Gerg Riccardi, File Structure, Addison Wesley