|
|
|
|
|
이페이지의 저작권은 |
||
|
제목: Bayer의 B-tree 논문번역 |
번역자에게 있습니다 |
|
|
번역: 정재준(rgbi3307@nate.com) |
최근수정일:2009-01-18 |
|
|
|
|
|
번역자 서문
|
이 문서는 R. Bayer 와 E. McCreight가 1970년 7월 논문으로 발표한 “대용량으로 정렬된 인덱스들의 구성과 관리” (원제: Organization and Maintenance of Large Ordered Indexes)를 번역한 것이다. 이 문서는 다른곳으로 이동 및 인용할 수 있으나, 번역자 정보와 출처를 기재하여 번역자의 노력을 보호해 주기 바란다. 아울러, 내용에 오류가 있는 부분은 번역자에게 이메일하여 바로잡아 가는 즐거움을 같이 누렸으면 한다. 몇십년 전에 이미 B-tree 이론을 정립한 R. Bayer와 E. McCreight의 과업에 이 번역물로 경의를 표한다. |
논문 원제목
|
ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES by R. Bayer and E. McCreight Mathematical and Information Sciences Report
No. 20 Mathematical and Information Sciences
Laboratory BOEING SCIENTIFIC RESEARCH LABORATORIES July 1970 |
개요
|
동적으로 무작위 접근하는 파일에 대한 인덱스의 구성과 관리를 고찰하였다. 인덱스가 디스크나 드럼과 같은 무작위 접근 백업장치에 저장되어 있다고 가정하였다. 인덱스는 키들을 검색, 삽입, 삭제할때 소요되는 시간이 logkI에 비례하도록 구성하였다. 여기서 I는 인덱스의 크기이고 k는 장치에 의존되는 자연수로서, 수행능력과 같은 것이며, 설계로 최적화 된다. 저장 장치의 이용도는 최소 50%이나 일반적으로 이것보다 더 높다. 인덱스의 페이지들은 특별한 데이터-구조체로 구성되며, 이것을 B-trees 라고 호칭한다. 설계는 분석되었고, 수행능력의 경계조건들은 수집되었고, 최적화된 k는 계산되었다. 100,000 키들을 인덱스화하여 실험들을 수행했다. 15,000(100,000) 크기의 인덱스는 2311 디스크를 갖춘 IBM 360/44에서 평균적으로 초당 9(최소 4) 트랜잭션들로 관리될 수 있다. 핵심 단어들과 구문들: 데이터 구조체들(Data structures), 무작위 접근 파일들(random access files), 동적 인덱스 관리(dynamic index maintenance), 키 삽입(key insertion), 키 삭제(key deletion), 키 검색(key retrieval), 페이징(paging), 정보 검색(information retrieval). |
1. 소개
|
이 논문에서 우리는, 동적으로 변화되는 무작위 접근 파일을 위한 인덱스의 구성과 관리 문제를 숙고하였다. 인덱스에 대해서 우리는, 물리적으로 데이터 요소들에 인접한 고정된 크기의 짝으로 이루어진 (x,a) 인덱스 요소들의 수집을 고려하였다. x는 키이고 몇가지 관련되는 정보는 a이다. x 키는 인덱스안에서 유일한 요소로 식별된다. 연관되는 정보는 무작위 접근 파일안의 레코드들의 집합이나 하나의 레코드를 가리키고 있다. 이 논문에서 연관되는 정보 a는 더이상 흥미로운 것이 아니다. 우리는 다음과 같은 사항을 가정했다. 인덱스 자체는 너무 부피가 커서, 이것의 작은 일부분만이 주저장소에 한번에 저장될 수 있다고 설정했다. 그래서 인덱스 묶음들이 몇몇 백업 저장소에 유지 되어 있어야 한다. 백업 저장소들의 등급은 가상의 무작위 접근 장치들로서 오랜 접근과 대기 시간이 소요되는 것으로 고려했다 - 자기코어 저장소와 같은 실제 무작위 접근 장치와는 대립되는것 - 그리고, 한번에 높은 데이터 비율로, 물리적으로 연속된 데이터 전송이 시작되는것이다. 전형적인 가상 무작위 접근 장치들은: 고정되어 움직이는 헤드 디스크들과 드럼들, 데이터 셀들이다. 데이터 파일은 자체적으로 변경되므로, 효율적으로 인덱스를 찾거나 데이터 요소들을 검색할 수 있어야 하며, 경제적으로 키들을 삽입하거나 삭제할 수 있어야 한다. 여기서 키들은 아주 정확한 인덱스 요소들이다. 이 논문에서 기술하는 인덱스 구성은 키들을 검색하고 삽입, 삭제가능하며 이때 소요되는 시간은 logkI에 비례하거나 더 빠르다. 여기서 I는 인덱스의 크기이고 k는 장치에 의존하는 자연수이다. 이 숫자는 페이지 크기로 기술하며, 설계를 검색하고 보수하여 수행능력이 최적화 되는 것이다. 묘사 가능한 이론적인 분석과 실제 실험들을 통하여 다음과 같은 내용들을 확인했다. 15,000 크기의 인덱스를 2311 디스크 백업 저장소를 갖춘 IBM 360/44 에서 실제적으로 초당 9번의 평균 검색과 삽입, 삭제 작업으로 관리가능하다. 우리의 이론적인 분석에 의하면, 1,500,000 크기의 인덱스를 실제적으로 위와 같은 환경에서 최소 2번의 트랜잭션으로 관리가 가능하다는 것이다. 인덱스는 고정된 크기의 페이지들로 구성되며 키들을 2k까지 보유한다. 그러나 페이지들은 부분적으로 채워진다. 페이지들은 주 저장소와 백업 저장장치 사이에서 정보를 전달하는 블럭들이다. 페이지 자체들은 B-tree라고 이름을 붙인 특성화된 트리 노드들이며 다음 섹션에서 기술한다.이 논문에서 이러한 트리들은 단지 하나의 방향으로 성장하고 접근하는데, 노드들이 하나의 형제로 분리되거나, 2개의 형제들이 병합되거나 단일 노드로 연결된다. 분리하고 연결하는 과정들은 잎들(leaves)에서만 시작되고 루트쪽으로 전개된다. 루트 노드가 분리되면, 새로운 루트가 나타나야 하고, 이것은 트리의 높이가 증가하는 유일한 방법이다. 트리가 줄어들면 반대 과정이 발생한다. 물론, 인덱스를 구성하기 위해서 해시-코딩과 같이 경쟁적으로 다른 설계들이 많이 있다. 대단위 응용들을 위해서, 이 논문에서 제시하는 설계는, 다른 것들에 비해서 다음과 같은 괄목할만한 장점을 제공한다: i) 저장소 이용률은 언제나 최소 50%이며 평균적으로 더 좋아진다. ii) 파일이 성장하고 접근되는 것처럼 저장소가 요청되고 배포된다. 저장소가 매우 많이 할당되어 있다면, 혼잡한 문제 또는 수행성 하락이 없다. iii) 키들의 순서는 관리되며 다음과 같은 순서를 기반으로 처리 된다: 선배자와 후배자들을 찾는다; 파일을 순차적으로 검색하여 쿼리들에 답변한다; 주어진 키를 시작으로 레코드들의 수를 검색하고 삭제, 스킵한다. iv) 검색과 삽입, 삭제들이 일괄적으로 나타나면, 본질적인 순차 처리과정으로 인덱스를 매우 효율적으로 처리하는 것이 가능한데, 이때 일괄작업 키들에 대한 작업들을 미리 정렬하거나 간단한 페이징을 미리하는 알고리즘으로 구현한다. 여러가지 다른 설계들이 동일하거나 매우 유사한 문제들을 해결하기 위해 시도되고 있다. [1]과 [2]에서 기술한 AVL-trees는 수행되는 시간이 log2I 라는 것이 보장되지만, 단지 1단계 저장에만 적용된다. [3]과 [4]에서 기술한 설계들은 log 대수적인 수행능력이 없다. 이 논문에서 발표하는 해결책은 새로운 것이며, 문제를 해결하려는 관점에서는 [1-4]에서 기술한 것들과 유사하게 연관되고, 트리 구조체들을 채택한 데이터 구성을 사용한다. |
2. B-Trees
|
정의.2.1: 정수형으로 h >= 0 이고, k는 자연수, 유도된 트리 T는 B-trees의 t(k,h) 클래스이다.이때 T는 비워져(h=0) 있거나 다음의 속성을 가진다. i) 루트에서 리프로 연결되는 각각의 경로는 동일한 길이인 h를 가지며, T의 높이라고도 호칭된다. 즉, h = 경로안의 노드들의 수. ii) 루트를 제외한 각 노드와 리프들은 적어도 k+1의 자식들을 가진다. 루트는 리프이거나 적어도 2개의 자식을 가진다. iii) 각 노드는 최대로 2k+1의 자식들을 가진다. B-Trees에서 노드들의수: B-tree T Î t(k,h) 에서 Nmin 과 Nmax를 각각 최소, 최대 노드들의 수라고 하자. 그러면,
h >= 2일때, 이것은 또한 h=1을 수용한다. 유사한 방법으로 다음을 얻는다.
T Î t(k,h) 노드들의 수인 N(T)의 상위와 하위 경계는 아래와 같이 주어진다.
t(k,h) 클래스들은 해체될 필요가 없다는것을 알아두자. |
3. 데이터 구조체와 검색 알고리즘
|
반복하면, 인덱스가 저장되어 있는 페이지들은 B-tree T Î t(k,h)의 노드들이고 2k 키들을 보유할 수 있다. 추가적으로, 인덱스를 위한 데이터 구조체는 다음과 같은 속성을 가진다. i) 루트를 제외한 각각의 페이지는 k와 2k사이의 수만큼 키(인덱스 요소)들을 보유한다. 루트 페이지는 1과 2k사이의 키들을 보유한다. ii) 페이지 P에 있는 키들의 수를 l(leaf가 아님)이라 하자. 그러면 P는 l+1개의 자식들을 가진다. iii) 각각의 페이지 P안에서 키들은 순차적으로 증가하는 순서이다: x1, x2, ..., xl; k <= l <= 2k 여기에서 1 <= l <= 2k 인 루트 페이지는 제외된다. 더 전개하면, P는 자식들과 연결되는 l+1개의 포인터들인 p0, p1,..., p1을 포함한다. 리프 페이지들에서는 이 포인터들이 정의되지 않는다. 논리적으로, 하나의 페이지는 그림1에서 보여주는바와 같이 구성된다.
그림1. 페이지의 구성 αi는 인덱스 요소 (xi, αi)내에서 연관된 정보이다. 세짝의 (xi, αi, pi)나 - 제한된 αi나 - 두짝의 (xi, pi)는 또한 엔트리로 호칭된다. iv) P(pi)를 pi가 연결시키는 페이지라고 하고, K(pi)를 그 페이지들에 있는 키들의 집합이라고 하자. 그러면, 여기서 고려하는 B-trees는 다음과 같은 조건들을 항상 유지한다:
그림2는 t(2,3)에 속하는 B-Tree의 예이며 위의 모든 조건들을 만족한다. 이 그림에서 αi는 보여주지 않는다. 그리고 페이지 포인터들은 점으로 된 그림으로 표현된다. 사각형 박스들은페이지들을 나타내고 바깥쪽에 있는 숫자들은 페이지 번호이며 나중에 사용된다.
그림2. 인덱스를 위한 t(2,3)의 데이터 구조체 검색 알고리즘: 그림3에 있는 플로우차트는 키 y를 검색하기 위한 알고리즘이다. p,r,s는 포인터 변수들이고 u로 표시한 것은 "정의되지않은" 값으로 가정할 수 있다. r은 루트를 가리키고, 트리가 비워져 있다면 u이고, s는 검색에서는 사용 목적이 없지만 삽입 알고리즘에서 사용될 것이다. p가 가리키는 페이지를 P(p)라고 하면, x1,...,xi들은 P(p)안의 키들이며 p0,...,pi는 P(p)안의 페이지 포인터들이다. 검색 알고리즘은 논리적으로 간단하지만, 컴퓨터에 이것을 프로그램하고자 한다면 효율적인 기술을 사용해야 한다. 즉, 이진 탐색으로 페이지를 스캔한다.
그림3. 검색 알고리즘 검색 비용: 페이지 트리의 높이를 h라고 한다면, 대부분의 h 페이지들이 스캔되고 백업 저장소에서 패치되어 키 y를 검색한다. 우리는 이제 크기가 I로 주어진 인덱스에서 h의 경계치를 유도해 낼 것이다. t(k,h)의 B-tree 페이지들안의 키들의 최소와 최대수인 Imin 과 Imax는:
이것은 h >= 1 일때, (2.1)로부터 즉시 산출된다. 그래서 우리는 높이 h에 대해서 뚜렷한 경계치를 가진다.
|
4. 키 삽입
|
그림4에 있는 알고리즘은 섹션3에서 기술한 인덱스로 단일키 y를 삽입하는 것이다. 변수 s는 검색 알고리즘에 의해서 마지막 페이지까지 스캔된 페이지 포인트이며, 페이지 트리가 비워져 있다면 u값을 가진다.
(1) 키 y는 인덱스에 이미 존재하므로, 적절한 행동을 취한다. 그림4. 삽입 알고리즘 페이지 분리: 엔트리를 삽입하고자 하는 페이지 P가 이미 가득차 있다면, 2개 페이지로 쪼개질 것이다. 논리적으로 첫째, 삽입하고자 하는 엔트리를 P안의 엔트리들의 순서로 삽입한다 - P는 주 저장소에 있다고 가정한다 - 결과적으로 엔트리들의 순서는 아래와 같다.
이제 서브순서
Q를 페이지 P의 아버지라고 하자. 엔트리
위의 삽입처리는 파라미터 k를 가진 B-trees에서 파라미터 k를 가진 B-trees로 진행되며, (3.1)과 (3.2), (3.3) 속성을 유지하고 있음을 알아두자. 삽입 과정을 보여주기 위해서, 파라미터 k=2인 그림5의 트리에 키 9를 삽입하면 그림2와 같은 결과가 된다.
그림5. t(2, 2)안의 인덱스 구조체 |
를 P에 넣고, 새로운 페이지인 P'를 도출하여 아래와 같은 서브순서를 이곳에 포함시킨다.
를 Q에 삽입한다.
를 Q에 삽입하는것은, 또한, Q를 쪼개야 하는 원인이 될 수 있으며, 루트쪽으로 계속 진행될 가능성이 있다.
를 포함시킨다.
5. 검색과 삽입 비용
|
인덱스를 관리하고 키를 검색하는 비용을 분석하기 위해서, 백업 저장소에서 메인 저장소로 패치되는 페이지들의 량과 백업 저장소에 저장되는 페이지량을 알아야 한다. 우리는 분석할 때 다음과 같은 가정을 설정했다: 페이지 내용을 점검 혹은 수정할때는 어떤 키를 한번의 동작으로 검색하거나 삽입, 삭제하는 동안 이루어 지며, 페이지 내용은 정확하게 한번씩만 패치 되거나 페이지 아웃된다. 메인 저장소에서 h+1 페이지들을 유지하기 위한 페이징 영역이 이러한 행동을 충족시켜준다는 것을 이 논문 설명 과정에서 명확하게 보여줄 것이다. 강력한 페이징 설계, 즉, 루트 페이지를 메인 저장소에 지속적으로 잠궈 두는 것은 패치나 페이지 아웃 되어야 하는 페이지들의 수를 감소시킬 것이다. 우리는 이러한 설계들을 분석하지는 않았지만 실험에서 사용은 했다. fmin(fmax)를 패치되는 페이지들의 최소(최대)수 라고 하고, ωmin(ωmax)를 쓰여지는(write) 페이지들의 최소(최대)수 라고 하자. 검색 비용: 검색 알고리즘에서 한개 키를 검색할때 명백히 아래와 같은 비용이 얻어진다. fmin = 1; fmax = h; ωmin = ωmax
= 0 삽입 비용: 한개 키 삽입에 대해서, 페이지 분리가 발생하지 않는다면 다음과 같은 최소 비용이 요구된다. fmin = h; ωmin = 1 루트 페이지를 포함하고 있는 검색 경로안의 모든 페이지들이 두개로 분리될때, 대부분의 작업 비용이 발행한다. 검색 경로가 h 페이지들을 포함하고 있고 새로운 루트 페이지를 쓰야 한다면, 아래와 같은 비용이 발행한다: fmax = h; ωmax = 2h + 1 h는 항상 이전 트리의 높이라는 것을 알아두자. 이러한 최악의 경계치가 명확하더라도, 한개의 키가 삽입될때 발생하는 일량을 측정하는 방법으로는 적당하지 않다. 키들이 검색되거나 삽입되는 것에 대한 인덱스를 고려할때, 키들이 삭제 되지는 않으므로, 다음과 같이 I 키들의 인덱스를 구축할때 평균적인 작업량 경계치를 도출할 수 있다: 각각의 페이지가 쪼개지는 것은 한개의 새로운 페이지가 생성되는 원인이 된다. (루트 페이지가 쪼개 질때는 두개) I 아이템들의 인덱스가 구축되는 동안 발생하는 페이지 분리수는 n(I)-1 이다. 여기서 n(I)는 트리에 있는 페이지들의 수이다. 각각의 페이지는 적어도 k개의 키들을 가지고 있으므로, 루트 페이지를 제외하면 이것은 단지 1을 가지므로, 우리는 다음을 얻는다:
각각의 단일 페이지가 분리되는 것은 최대 2개의 추가적인 페이지들이 쓰여지는 원인이 된다. 따라서, 페이지 분리로 인한 단일 키 삽입에 대해서, 페이지들이 쓰여지는 평균적인 숫자는 다음과 같이 산출된다.
페이지 분리가 추가적인 페이지 검색을 요구하지는 않는다. 따라서 삭제가 없는 인덱스에 대한 단일 삽입의 평균 비용은 다음과 같이 산출된다.
|
6. 삭제 처리
|
동적으로 변화되는 인덱스내의 키들을 지워야 하는 경우가 있을 수 있다. 그림6의 알고리즘은하나의 키 y를 인덱스로부터 삭제하고, 우리의 데이터 구조체를 적절하게 관리한다. 첫째로 yi로 언급되는 키를 위치시킨다. 데이터 구조체를 적절하게 관리하기 위해서, yi가 리프에 있다면 삭제되고, 그렇지 않다면 서브트리에서 가장 작은 키로 교체되어야 한다. 서브트리의 루트는 P(pi)이다. 가장 작은 키는 p0 포인트가 리프 페이지를 가르키는 것을 따라가는 P(pi)로 부터 발견된다. 리프 페이지를 L이라 하고 여기에 첫번째 키가 보관된다. 그런다음, 이 키를 xi라 하고 L로부터 삭제된다. 결과적으로 L은 k 키들보다 적게 보관하고, L과 이웃하는 형제사이의 연결 혹은 언더플로우가 수행된다.
(1) 삭제하고자 하는 키가 인덱스에 없으므로 적절한 행동을 취한다. 그림6. 삭제 알고리즘 연결: P와 P' 2개의 페이지들을 이웃 형제들이라고 부르며 이들은 같은 아버지인 Q를 가진다. 그리고 이들은 Q에서 이웃하고 있는 포인터들에 의해서 연결된다. P와 P'가 함께 2k 키들보다 적게 가지고 있다면, 연결 시킬 수 있으며, 3개의 페이지들은 다음과 같은 형태이다:
2개의 페이지가 다음과 같이 교체된다:
엔트리 (yj, p')가 Q로부터 삭제되는 결과로 Q는 k 키들보다 적은 수를 포함하고 Q에 대해서 특별한 행동이 발생한다. 이 처리는 트리의 루트 방향인 위로 전개될 것이다. 언더플로우: P와 P'에 있는 키들의 합계가 2k보다 크면, P와 P'에 있는 키는 동등하게 분배될 수 있으며, 이 처리를 언더플로우라고 하며, 다음과 같다: P와 P'를 연결하여 매우 큰 P를 만든다. 이것은 P가 메인 저장소에 있기 때문에 가능하다. 이제 섹션4 - 몇가지 명백한 미러 수정들이 있는 - 에서 기술한 대로 P를 중간지점에서 분리한다. 언더플로우는 전이되지 않는다는 것을 알아두자. Q는 수정되었지만, 여기에 있는 키들의 수는변화되지 않는다. 삭제 과정을 확인해 보기 위해, 그림2에 있는 인덱스를 고려하여 키 9를 삭제하면, 그림5에 있는 인덱스 결과가 된다. |
7. 삭제 비용
|
삭제하고자 하는 키 y가 인덱스내에 있다면, 성공적으로 삭제되며, y가 리프에 존재하고 연결 혹은 언더플로우가 발생하지 않는다면 최소의 작업량으로 작업된다. 이것의 비용은:
y가 리프에 없고 연결 혹은 언더플로우가 발생하지 않으면,
검색 경로에 있는 첫번째 페이지 두개가 연결되거나, 검색 경로에 있는 루트의 아들에서 언더플로우가 발생하거나, 루트가 변경되면 최대의 작업량으로 수행된다. 이것의 비용은:
삽입 처리하는 경우에는 경계값들의 산출이 명확하지만, 매우 멀리 흩어져 있고 병적인 예제들은 제외하여 드물게 가정된다. 어떤 키를 삭제하기 위해 필요한 평균적인 작업량을 좀더 유용한 형태로 측정하기 위해, 인덱스 I에 있는 모든 키들이 삭제되는 동안 "순수 삭제 처리" 된다는 것을 도입하기로 한다. 이때 삽입되는 키들은 없다. 순간적인 연결과 언더플로우를 무시한 상태에서, 각각의 삭제마다 최악으로 f1=h 와 ω1=2를 얻게 된다. 그러나, 키들이 항상 루트 페이지에서 삭제된다면 이것은 최상의 경계치가 된다. 각각의 삭제는 최대로 하나의 언더플로우를 발생시키며, 이때 필요한 비용은 f2=1의 추가적인 패치와 ω2=2의 추가적인 쓰기이다. 가능성 있는 연결들의 전체 수는 n(I)-1로 산출되며, 이것은 최대로 (I-1)/k 이다. 각각의 연결은 추가적인 패치 1과 추가적인 쓰기 2을 발생시키며, 이것은 평균적으로 다음과 같은 결과가 된다.
그래서 평균적으로 아래를 얻는다:
|
8. 페이지 오버플로우와 저장소 사용률
|
백업 저장소의 사용률을 중요하게 고려하지 않은 설계에서는 극단적인 경우 50% 이하의 사용률을 나타낸다. 이때 루트 페이지는 포함되지 않으며, 모든 페이지들이 k키 만을 포함하고 있는 경우이다. 페이지 분리를 방지하게 되면 사용률이 향상될 수 있다. 두개의 페이지가 서로 이웃한 형제 페이지 P와 P'사이의 오버플로우는 다음과 같이 수행된다:어떤 키가 P에 삽입되어야 하고 P는 이미 가득차 있으나, P'는 가득차지 않았다고 가정하자. 그러면, 키가 P에 있는 키-순서대로 삽입되고, 섹션6에서 기술한 언더플로우가 결과적인 순서와 P' 사이에서 수행된다. 이것은 P가 두개 페이지들로 분리되는 것을 방지한다. 그러므로, 두개가 서로 이웃한 형제들 모두가 가득찬 경우에 페이지 분리가 일어날 것이며, 그렇지 않은 경우에는 오버플로우가 발생한다. 삭제가 없는 인덱스에는 오버플로우들이 최악의 경우 약66%까지 저장소 사용률을 증가시킬 것이다. 삽입과 삭제 둘다 발생한다면, 저장소 사용률은 50%까지 내려갈 것이다. 대부분의 실용적인 응용들에서는 오버플로우를 적절하게 도입하여 저장소 사용률을 증가 시켜야 한다. 또한, 오버플로우와 언더플로우, 연결들을 지원하기 위해서 서로 이웃한 형제들만 사용하는 것보다 좀더 큰 동네사람들을 고려하여 소형의 저장소 점유률을 증가시킨다. 오버플로우가 있는 설계에서 삽입들의 비용 경계치는 다음과 같이 쉽게 유도 된다:
순수한 삽입 처리에서는, 평균 비용으로 아래와 같은 경계값이 도출된다:
각각의 삽입으로 인해서 오버플로우를 발생기키는 예제들을 작성하는 것은 쉽다. 이러한 경계값들을 많이 향상 시키기 위해서는 삽입 처리에 대해서 특별한 가설들이 있어야 한다. |
9. 삽입과 삭제들이 있는 인덱스 관리 비용
|
이 논문의 주목적은 인덱스를 경제적으로 관리할 수 있는 데이터 구조체를 개발하는 것이다. 여기서 인덱스는 검색과 삽입, 삭제 작업들이 자유롭게 실행되어야 한다. 우리는 이제 이러한 환경에서 처리 비용의 경계치들을 유도할 것이다. 검색 비용 경계값 산출은 삽입 혹은 삭제들의 순서에 대해서 어떠한 가설도 만들 필요없이 언제나 타당하다. 또한, 삽입과 삭제들의 최대 및 최소 경계값들은 가설 설정없이 언제나 타당하게 유도된다. 삽입과 삭제들이 혼합되어 있는 경우에는, 평균비용으로 산출되는 경계값들이 항상 유효하지 않다. 아래의 예제는 평균비용 상한치가, 단일 검색 혹은 삭제시 유도된 비용의 상한치를 적절하게 개선하지 못한다는 것을 보여준다. 예제: 그림2에 있는 트리를 T2, 그림5에 있는것을 T5라고 하자. T2에서 key 9를 삭제하여 T5를 이끌어 내고, T5에 key 9를 삽입하여 T2로 되돌린다. key 9를 삭제하고 삽입하는 교체 순서를 T2를 시작으로 하여 적용해 보도록 하자. 사례1: 페이지 오버플로우는 없으나 페이지 분리는 발생함: i) T2에서 key 9를 삭제할때 요구되는 사항: 3번의 검색으로 key 9를 위치 시킴. 페이지들 이름은 1,2,6. 페이지 6에서 형제 5를 1번 검색하여 발견함. 이때 페이지 5와 6은 연결됨. 페이지 이름이 5와 2인 두개의 페이지들은 수정되고 쓰여짐. 페이지 6과 3은 트리 T2에서 지워짐. 그래서,
ii) T5에 key 9를 삽입시 요구사항: 2번의 검색으로 페이지 5에 9를 위한 슬롯을 위치시킴. 페이지들 다섯개가 쓰여짐, 페이지 이름은 1,2,3,5,6. 그래서,
사례2: 페이지 오버플로우가 발생하는 설계에 대한 고찰. i) key 9를 삭제하는 것은 사례1과 같은 결과를 도출해냄. ii) key 9를 삽입시 요구사항: 2번의 검색으로 페이지 5에 9를 위한 슬롯을 위치시킴. 4와 7 형제들을 2번 검색하여 찾아낸 5는 분리됨. 다섯개의 페이지들이 사례1처럼 쓰여짐. 그래서:
임의의 h와 k에 대해서 유사한 예제들을 구성할 수 있다. 분석을 통해서, 우리 설계의 수행능력은 삽입들과 삭제들의 실제 순서에 의존한다는 것을 명확하게 알았다. 삽입들과 삭제들 사이의 상호 간섭은 설계의 수행능력을 저하 시킨다. 이것은 삽입 혹은 삭제만 하는것과 대립된다. 최악의 경우에 이러한 상호 간섭은 팩터 3에 의해 수행능력을 저하시킨다. 이러한 상호 간섭은 의문점으로 열려져 있으며, 실제 응용들에서도 나타나며, 우리가 어떻게 최악의 경우를 분석하여 현대적으로 개선하는가가 중요하다. 유도할 수 있는 비용의 경계값들이 최악의 상태이라도, 우리의 실험에서 오버플로우들이 있는 설계가 오버플로우들이 없는 설계보다 더 우수하게 수행되었다.
그림7. 키를 단일 검색 혹은 삽입, 삭제시 비용 테이블 |
10. k의 선택
|
우리 설계의 수행능력은 파라미터 k에 의존한다. 따라서, k를 신중하게 선택해서 수행능력을 가능한 좋게 만들어야 한다. 설계의 수행능력을 아주 개략적으로 도출하기 위해서, 우리는 아래와 같은 가설들을 설정한다: i) 각각의 페이지가 저장되거나 패치될때 소모되는 시간은 다음과 같은 형태로 표현할 수 있다:
α. 페이지당 소모되는 고정된 시간, 즉, 평균 디스크 탐색시간 더하기 고정된 CPU 오버헤드, 등. β. 페이지 엔트리당 전송 시간. r. 시간의 log 대수적 부분의 상수, 즉, 이진 탐색 때문. ν. 평균 페이지 점유를 위한 요소, 1 <= ν <= 2. 페이지 변경이 페이지 안에서 키들을 옮기도록 요구하지 않지만, 필요한 채널 하위 명령들이 발생되어, 주저장소에서 정보의 여러 조각들을 연결하여 하나의 페이지를 작성한다는 것을 가정한다. 페이지를 패치하고 저장하는 작업이 동시에 발생하기 때문에 우리는 이러한 가설을 설정했다. i) 검색과 삽입, 삭제 작업들이 혼합된 환경에서 단일 작업단위당 패치되고 저장되는 페이지들의 평균 수는 대체적으로 - 그림7에서 보여주는 바와 같이 - h에 비례하며, δh라 한다. 작업단위당 소모되는 전체시간 T는 다음과 같이 유추될 수 있다:
유추된 h는:
k가 아래와 같이 선택된다면, 이제 우리는 쉽게 Ta의 최소치를 산출할 수 있다:
CPU 시간을 무시한 상황에서, k는 백업 저장소로 사용되는 장치 특성을 나타내는 숫자이다. 우리의 실험 예제에서 적절한 페이지 크기를 산출하기 위해서, α = 50ms 그리고 β = 90μs라고 가정했다. 그림8에 있는 테이블에 의하면, 적용 가능한 선택은 64 < k < 128 이 될수 있다. 프로그램 편의성으로 인해서 우리는 결과적으로, 120 엔트리의 페이지 크기안에 k=60을 선택했다.
그림8. 적절한 k를 선택하기 위한 함수 f(k,v) k=60일때, 특정 높이의 페이지 트리안에 저장될 수 있는 인덱스의 크기를 아래의 그림9에서 보여줄 수 있다.
그림9. 페이지 트리의 높이와 인덱스 크기 |
11. 실험 결과들
|
여기서 제시한 알고리즘들은 프로그램 되었고, 수행능력은 다양한 실험방식으로 측정 되었다. 프로그램들은 백업 저장소인 2311 디스크 장치가 장착된 IBM 360/44 컴퓨터에서 실행 되었다. 인덱스 요소 크기는 (14 8-비트 캐릭터)로 선택되었고 인덱스 크기는 일반적으로 (약 10,000 인덱스 요소들)로 사용되었다. 이 단위에서 기계적인 평균 접근 대기시간은 약 50ms 이고, 이후, 정보 전송은 인덱스 요소당 약 90μs 정도 걸린다. 이러한 두개의 파라미터를 고려한 우리의 분석은, 120 인덱스 요소들 상에서 페이지의 크기가 (2k)가 적절하다는 것을 예측했다. 프로그래밍은 간단히 요구된 페이징 설계를 포함시켜 코어 저장소(약 1,250 인덱스 요소들의 최악)를 활용할 수 있는 장점을 살렸고, 물리적인 디스크 동작들의 회수를 줄이는 방향으로 시도했다. 다음 섹션인 가상 디스크 읽기에서, 우리는 디스크 페이지를 코어에서 활용할 수 있는 페이징 설계를 요청할 것이다; 가상 디스크 읽기는 물리적인 디스크 읽기와 같은 결과여서, 요청한 디스크 페이지의 복사본 없이 코어 저장소가 페이징 영역이 된다. 가상 디스크 쓰기도 이와 비슷하게 정의된다. 10개 실험들이 수행되었다. 이 실험들은 수행능력과 저장소 사용률을 어떤 방식으로 측정할 것인지에 대한 아이디어를 우리에게 제공한다. 다음의 내용을 선택하여 실험 명세서를 구성하도록 하자. 1) 삽입 작업시 오버플로우들의 허락 여부 2) 페이지당 인덱스 요소들의 수 3) 비어있는 인덱스를 초기화하기 위한 작업단위들의 순서 실험이 진행되는 동안 여러가지 관점에서, 몇몇 수행능력 변수들이 기록 되었다. 다양한 수행능력 측정들을 위한 알고리즘들에서 다음과 같은 내용들을 재치있게 추론할 수 있다. 1) 저장소 사용률 % 2) 작업단위(트랜잭션)당 가상 디스크 읽기 평균 수 3) 작업단위당 물리적 디스크 읽기 평균 수 4) 삽입 혹은 삭제시 가상 디스크 쓰기 평균 수 5) 삽입 혹은 삭제시 물리적인 디스크 쓰기 평균 수 6) 초당 작업단위들의 평균 수 이제, 실험들을 요약한다. 각각의 실험은 여러가지 단계들로 나누어져 있고, 이것들이 각각 종료되는 시점에서 수행능력 변수들이 측정되었다. 단계들은 괄호안의 번호들로 표시했다. E1: 페이지당 25 요소들, 오버플로우 허락함. (1) 키를 순차적으로 10,000개 삽입. (2) 키의 공간에서 균등하게 무작위로 삽입작업 50개, 검색작업 50개, 그리고 삭제작업 100. E2: 페이지당 120 요소들; E1과는 다르게. E3: 페이지당 250 요소들; E1과는 다르게. E4: 페이지당 120 요소들; 오버플로우 허락. (1) 키를 순차적으로 10,000개 삽입. (2) 키의 공간에서 균등하게 무작위로 검색작업 1,000개. (3) 순차적인 삭제작업 10,000개. E5: 페이지당 120 요소들, 오버플로우 허락하지 않음. (1) 키의 공간에서 균등하게 무작위로 삽입작업 5,000개. (2) 키의 공간에서 균등하게 무작위로 검색작업 1,000개. (3) 키의 공간에서 균등하게 무작위로 삭제작업 5,000개. E6: 오버플로우 허락함; E5와 다르게. E7: 페이지당 120 요소들, 오버플로우 허락함. (1) 키를 순차적으로 5,00개 삽입. (2) 키의 공간에서 균등하게 무작위로 각각 6,000개의 삽입작업과 검색작업, 삭제작업. E8: 페이지당 120 요소들, 오버플로우 허락함. (1) 키의 공간에서 균등하게 무작위로 삽입작업 15,000개 (2) 키의 공간에서 균등하게 무작위로 각각 100개의 삽입작업과 검색, 삭제작업 E9: 페이지당 250 요소들; E8과는 다르게. E10: 페이지당 120 요소들, 오버플로우 허락함. (1) 키를 순차적으로 100,000개 삽입. (2) 키의 공간에서 균등하게 무작위로 각각 1000개의 삽입작업과 삭제, 검색작업. (3) 키의 공간에서 균등하게 무작위로 100개의 그룹 검색, 여기서 그룹은 100개의 연속적인 키들의 순서 (10,000개의 트랜잭션들을 기반으로 한 통계들). (4) 키를 순차적으로 10,000개 삽입, 단계 (1)에서 삽입한 요소들을 균등하게 병합.
* 이 통계치는 불필요하게 크다, 왜냐하면 삭제 방법이 프로그램 되었기 때문이다. 가상 읽기에 필요한 수를 찾기위해, 순차적인 삭제을 위해서는 보여준 숫자에서 하나을 빼고, 무작위 삭제를 위해서는 하나를 뺀 결과에 0.5를 곱한다. |
참고 문헌
|
1. Adelson-Velskii, G. M., Landis, E. M.: 정보 구성 알고리즘. DANSSSR, 146, 263-266 (1962). 2. Foster, C. C.: 정보 저장소 그리고 AVL 트리들을 사용한 검색. Proc. ACM 20th Nat'l. Conf. 192-205 (1965). 3. Landauer, W. I.: 균형잡힌 트리 그리고 정보 검색에서 이것의 사용. IEEE Trans. on Electronic Computers, Vol. EC-12, No. 6, December 1963. 4. Sussenguth, E. H., Jr.: 파일들을 처리하기 위한 트리 구조체들의 사용. Comm. ACM, 6, No. 5, May 1963. |
|
Prof. Dr. R. Bayer Dept. of Computer Science Purdue University Lafayette, Ind. 47907 U.S.A. |
Dr. E M. McCreight Palo Alto Research Center 3180 Porter Drive Palo Alto, Calif. 94304 U.S.A. |
|
|
|
|
|
|
|
|
|
이페이지의 저작권은 |
||
|
제목: Bayer의 B-tree 논문번역 |
번역자에게 있습니다 |
|
|
번역: 정재준(rgbi3307@nate.com) |
최근수정일:2009-01-18 |