인덱스된 순차적인 파일 접근과 B+TREE
순차적인 인덱스 접근
- 인덱스된 순차적인 파일 구조는 두 가지 관점중에 하나를 선택한다.
인덱스된 : 파일은 키로 색인된 레코드 집합으로 볼 수 있다. 순차적인 : 파일에 순차적으로 액세스 할 수 있으며, 키별로 레코드를 순서대로 반환할 수 있다.
-
결과적으로 우리는 모든 레코드를 키로 순서대로 검색하고자 한다.
-
파일 시스템의 레코드는 엔트리 시퀀스가 있으므로 정렬하지 않고, 키로 순서대로 검색하는 유일한 방법은 바로 인덱스를 통해서 검색하는 것이다.
B 트리
-
B트리는 디스크나 다른 직접 접근 보조 기억 장치에서 잘 동작하도록 설계된 균형이 잡힌 검색 트리이다.
-
B-트리는 레드 블랙 트리와 비슷하지만, 디스크 입출력(I/O) 연산을 최소화하는데 있어서 더 낫다.
-
B-트리는 B-트리의 노드가 자식을 수십개에서 수 천개까지 가질 수 있다는 점에서, 레드 블랙 트리와는 다르다.
-
B-트리의 내부 노드가 N 개의 키를 포함한다면 N + 1의 자식을 가지게 된다.
-
노드에 있는 키들은 노드의 의해서 처리되는 키의 범위를 N + 1개의 부분 범위로 분할하는데 사용된다. 그리고 각각의 부분 범위는 자식에 의해서 처리된다.