Chapter 17: 파일 및 물리적 데이터베이스 설계를 위한 인덱싱 구조

Chapter Outline (장 목차):

인덱싱 구조: 이미 일부 주요 구성으로 된 파일이 있다고 가정합니다.

정적 인덱스

단일 수준의 정렬된 인덱스

주요 인덱스, 클러스터링 인덱스 및 보조 인덱스

다중 수준 인덱스

ISAM: 정적 인덱스

동적 인덱스

다중 수준 트리 기반 인덱스: B+-트리 (단일 수준: 매우 드물다)

소개:

왜 인덱스(색인)인가? (추가 보조 액세스 구조)

특정 검색 조건에 대한 레코드 검색 속도를 높이기 위해 사용됩니다.

예: 교과서의 1245페이지에 있는 "색인" 섹션을 참조하십시오. 왜 여기에 있을까요?

인덱스 구조는 기본 데이터 파일의 레코드의 물리적 배치에 영향을 미치지 않으면서 보조 액세스 경로를 제공하는 "디스크의 추가 파일"입니다.

인덱스 구조는 인덱싱 필드를 기반으로 레코드에 효율적으로 액세스할 수 있도록 합니다.
어떤 필드든지 인덱스를 생성하는 데 사용할 수 있습니다.

서로 다른 필드에 대한 여러 인덱스를 생성할 수 있습니다.

여러 필드에 대한 (다중 수준) 인덱스를 생성할 수 있습니다.
같은 파일에 대한 두 유형의 인덱스

인덱싱 필드에 대한 검색 조건을 기반으로 데이터 파일에서 레코드를 찾으려면 인덱스 파일을 검색하여 필요한 레코드가 위치한 하나 이상의 디스크 블록으로 이어지는 포인터를 안내합니다.

인덱스를 구성하려면 대부분의 인덱스가 정렬된 파일을 기반으로 하며 트리 데이터 구조(다중 수준 인덱스의 경우 B+-트리 등)를 사용합니다.

단일 수준의 정렬된 인덱스 유형:

정렬된 인덱스 (Ordered Index):

아이디어: 교과서에 사용되는 인덱스와 유사합니다.

알파벳 순서로 "중요한 용어" (인덱스 키와 유사)와 해당 용어가 책에서 나타나는 페이지 번호(블록 주소와 유사) 목록을 표시합니다.

인덱싱 필드(속성)

보통 인덱스 구조가 정의된 파일의 단일 필드.
인덱스 필드의 각 값은 해당 필드 값이 있는 레코드를 포함하는 모든 디스크 블록에 대한 포인터 목록과 함께 인덱스 파일에 저장됩니다.

인덱스 내 값들은 "정렬"되거나 "정렬"됩니다.

왜냐하면 인덱스에서 이진 검색(선형 검색 대신)을 수행하기 위해서입니다.

인덱스 파일은 데이터 파일보다 훨씬 작습니다. 왜일까요?

여러 유형의 정렬된 인덱스:

주요 인덱스 (Primary Index):

정렬된(정렬된) 레코드 파일의 정렬 키 필드에 지정됩니다.

클러스터링 인덱스 (Clustering Index):

비 키 정렬 필드에 지정됩니다(많은 레코드에서 동일한 값을 가짐).

(물리적) 데이터 파일은 클러스터링된 파일이라고 부릅니다.

파일은 최대 하나의 물리적 정렬 필드만 가질 수 있으므로 주요 인덱스 또는 클러스터링 인덱스 중 하나를 가질 수 있지만 둘 다 가질 수는 없습니다.

보조 인덱스 (Secondary Index):

파일의 어떤 비 정렬 필드에 지정됩니다.
데이터 파일은 여러 보조 인덱스를 가질 수 있습니다.

주요 색인 (Primary Indexes):

두 개의 필드로 구성된 인덱스 레코드(엔트리)를 포함하는 정렬된 파일:

주요 키 (Primary key): K(i)

블록의 첫 번째 레코드에 대한 주요 키 필드의 값

디스크 블록에 대한 포인터: P(i), 여기서 i는 특정 인덱스 엔트리를 나타냅니다.

여기서 디스크 블록은 해당 키 값이 있는 블록입니다.

데이터 파일:

제16장 슬라이드 38
정렬 키 필드: 이름
주요 키: 이름이 고유하다고 가정합니다.
각 블록의 첫 번째 레코드

인덱스 파일 (주요 인덱스)

인덱스의 각 항목은 다음과 같습니다:

<K(i), P(i)>: 여기서

K(i): 인덱스 항목 i의 이름 값
P(i): 인덱스 항목 i의 포인터

예:

<K(1) = (Aaron, Ed), P(1) = 블록 1의 주소>
<K(2) = (Adams, John), P(2) = 블록 2의 주소>
<K(3) = (Alexander, Ed), P(3) = 블록 3의 주소>

색인의 특징:

색인은 밀집형(dense) 또는 희소형(sparse)일 수 있습니다.

밀집형 인덱스는 데이터 파일의 모든 검색 키 값(즉, 모든 레코드)에 대한 인덱스 항목이 있습니다.
희소형 인덱스는 일부 검색 값을 위해서만 항목이 있습니다.

다른 이름으로 비밀집형 인덱스라고도 합니다.
인덱스 항목은 파일 내 레코드 수보다 적습니다.

주요 인덱스의 경우 일반적으로 밀집형 또는 희소형 중 어떤 것인가요?

주요 인덱스의 경우 두 가지 이유로 인해 인덱스 파일이 데이터 파일보다 훨씬 작습니다.

데이터 파일의 레코드 수보다 인덱스 항목이 적습니다.

각 인덱스 항목은 데이터 레코드보다 일반적으로 작으며 오직 두 개의 필드 또는 (키, 블록 주소)만 가지고 있기 때문입니다.

따라서 인덱스 파일에서 이진 검색은 데이터 파일에서 이진 검색보다 적은 블록 액세스를 필요로 합니다.

데이터 파일에서 인덱스 없이 블록 액세스 수 계산:

예 1) 블록 크기 B = 4 K바이트인 디스크에 저장된 r = 300,000개 레코드가 있는 정렬된 파일.

파일 레코드는 고정 크기이며 spanned되지 않았으며 레코드 길이 R = 100바이트.
bfr: 블록당 레코드 수 (간단히 K바이트 = 1000바이트로 가정)
파일에 필요한 블록 수: ceiling(r / bfr) = ?
데이터 파일에서 이진 검색을 몇 번 수행하나요?

주요 인덱스 파일을 통한 블록 액세스 수 계산:

주요 인덱스 파일에서 주어진 b 블록의 경우

인덱스 파일을 통한 레코드 검색의 경우 # 블록 액세스 = log2b + 1

log2b를 왜 사용하나요? 왜 1인가요? 슬라이드 9의 "Akers, Jan"이라는 이름 값을 가진 레코드에서 이진 검색을 시도해보세요.

예 1'): 블록 크기 B = 4 K바이트인 디스크에 저장된 r = 300,000개 레코드가 있는 정렬된 파일.

파일의 정렬 키 필드(V): 9바이트

블록 포인터(P): 6바이트.

각 인덱스 항목(레코드)의 크기 (Ri): (9 + 6) = 15바이트.

인덱스 파일의 bfr: 블록당 항목 수

인덱스 항목 = 항목 수

그렇다면 인덱스 파일의 크기는 얼마인가요?

인덱스 블록 = 항목 수 / bfr = 블록 수

인덱스 파일을 통한 이진 검색 수 = 블록 액세스 수

비인덱스 방법 대비 얼마나 개선되었나요?

주요 인덱스의 문제점:

주요 문제: 레코드의 삽입 및 삭제

데이터 파일의 "올바른" 위치에 레코드를 삽입하려고 시도하면

새 레코드의 공간을 만들기 위해 레코드를 이동할 뿐만 아니라
일부 인덱스 항목을 변경해야 합니다.
레코드를 이동하면 일부 블록의 앵커가 변경됩니다.

삽입을 어떻게 해결할까요?

정렬되지 않은 오버플로우 파일 사용
데이터 파일의 각 블록에 대한 오버플로우 레코드의 연결 목록 사용
해시 기법에서 오버플로우 레코드 다루는 방식과 유사
검색 시간을 개선하기 위해 각 블록과 해당 오버플로우 연결 목록 내에서 레코드를 정렬합니다.

삭제를 어떻게 해결할까요?

삭제 표시자 사용

군집 색인 (Clustering Indexes):

파일 레코드가 물리적으로 "비-키 (non-key)" 필드에 따라 정렬되어 있고 각 레코드에 대해 중복 값이 허용되는 경우,

군집 필드 (Clustering field): 이러한 비-키 필드입니다.

군집 파일 (Clustered file): 군집 필드를 가진 이러한 데이터 파일입니다.

군집 색인 (Clustering index): 또 다른 유형의 비밀집 인덱스입니다. 왜냐하면?

동일한 군집 필드 값을 가진 모든 레코드의 검색을 가속화하기 위해 생성되고 사용됩니다.

주요 색인과 어떤 차이가 있나요?

두 개의 필드로 구성된 정렬된 파일로서 다음과 같습니다.

군집 필드와 동일한 유형의 필드

디스크 블록 포인터

인덱스 항목: <(각 다른) 값 v, v를 가진 데이터 파일의 첫 번째 블록에 대한 포인터

데이터 파일: EMPLOYEE 파일

Dept_number: 순서가 지정된 비키 필드 (군집 필드)

인덱스 파일 (군집 색인):

인덱스의 각 항목은 다음과 같습니다:

<K(i), P(i)>, 여기서
K(i): 인덱스 항목 i의 군집 필드 값
P(i): 인덱스 항목 i의 포인터

정렬됨
예:

<K(1) = 1, P(1) = 블록 1의 주소>
<K(2) = 2, P(2) = 블록 1의 주소>
<K(3) = 3, P(3) = 블록 2의 주소>

군집 색인의 문제점:

여전히 주요 문제: 레코드의 삽입 및 삭제

왜? 물리적으로 정렬되어 있기 때문입니다.

삽입/삭제를 어떻게 해결할까요?

군집 필드의 각 (다른) 값에 대해 전체 블록 (연속 블록 클러스터)을 예약

이렇게 하면 해당 다른 값으로 모든 레코드가 (동일한) 블록 (또는 블록 클러스터)에 배치됩니다.

이로써 삽입/삭제가 비교적 간단해집니다.

군집 색인을 사용한 블록 액세스 수 계산:

예 1'') 블록 크기 B = 4 K바이트인 디스크에 저장된 r = 300,000개 레코드가 있는 정렬된 파일.

Zipcode (군집 필드)로 정렬되어 있다고 가정합니다.

파일에는 1,000개의 서로 다른 우편 번호가 있으며, 코드가 균등하게 분포되어 있다고 가정하면 각 우편 번호 당 평균 300개의 레코드가 있습니다.

인덱스 항목 (ri): ?

i번째 인덱스 레코드의 크기: 5바이트 우편 번호 + 6바이트 블록 포인터

레코드 길이 (Ri): 11바이트

bfri: 블록당 레코드 수

인덱스 블록 = ceiling(ri / bfri) = ? 블록

군집 색인 파일에서의 이진 검색 수 = ? 블록 액세스

군집 색인 파일을 통한 데이터 레코드 검색의 경우 # 블록 액세스 = ? 블록 액세스

보조 색인 (Secondary Indexes):

데이터 파일에 대한 보조 수단으로서의 역할을 제공합니다.

일부 기본 액세스가 존재합니다.
데이터 레코드의 정렬은 중요하지 않을 수 있으며 해싱될 수 있습니다.

다음과 같은 경우에 생성될 수 있습니다.

모든 레코드에서 고유한 값을 가진 키 필드 또는

중복 값이 있는 비-키 필드.

두 개의 필드로 구성된 정렬된 파일:

인덱싱 필드, K(i): 데이터 파일의 어떤 비-순서 필드와 동일한 유형

레코드 (왜?) 또는 블록 포인터 (왜?), P(i): 인덱싱 필드 값을 포함하는 레코드 또는 블록을 가리키는 포인터

동일한 데이터 파일에 여러 보조 색인을 생성할 수 있습니다.

각각은 특정 필드를 기반으로 파일에 액세스하는 추가적인 방법을 나타냅니다.

키 필드에 대한 보조 색인:

키 필드: 모든 레코드에 대해 고유한 값을 가집니다.

이런 이유로 보조 키라고도 합니다.

어떤 고유한 키 필드 (또는 기본 키 속성)에 해당합니다.

이 경우, 데이터 파일의 각 레코드에 대한 하나의 인덱스 항목이 있습니다.

각 인덱스 항목은 두 가지 구성 요소를 가지고 있습니다:

<레코드의 필드 값,
레코드를 포함한 블록 또는 레코드 자체를 가리키는 포인터>

이러한 유형의 보조 색인은 밀집형인가 아닌가요?

비-순서 키 필드에 대한 밀집형 보조 색인

블록 포인터를 사용합니다.

다음은 "보조 색인 파일을 통한 블록 접근 횟수 계산"에 관한 내용입니다.

보조 색인 파일을 통한 블록 접근 횟수 계산:

예 1’’) 크기가 R = 100 바이트인 고정 길이 레코드를 가지는 r = 300,000 레코드가 있는 정렬된 파일이 있으며, 이 파일은 블록 크기 B = 4 K바이트인 디스크에 저장되어 있습니다.

파일은 b = 7,500개의 블록으로 구성됩니다 (이전에 계산한 값입니다).

이 파일에서 두 번째 키에 특정 값을 가진 레코드를 찾고자 합니다. 즉, 파일의 비-순서 키 필드 중 하나입니다.

두 번째 키 필드: 9 바이트 길이, 블록 포인터: 6 바이트입니다. (만약 보조 색인이 없다면 평균적으로 b / 2 = 7,500 / 2 = 3,750개의 블록 접근이 필요한 선형 검색이 될 것입니다.)

이 파일의 비-순서 키 필드에 대한 보조 색인을 생성한다고 가정합니다.

각 인덱스 항목 크기 = (9 + 6) = 15 바이트

bfr = ? 개의 항목 per 블록

밀집형 인덱스 항목 수 = 데이터 파일의 레코드 수 = ? 개의 항목

필요한 인덱스 블록 수 = ? 개의 블록

이 인덱스를 통한 이진 검색에 필요한 블록 접근 수: ? 개의 블록 접근

인덱스를 사용하여 레코드를 검색하는 데 필요한 블록 접근 수: ? 개의 블록 접근

기본 색인보다 "더 많은" 블록 접근이 필요한 이유는 무엇인가요?

주된 색인이 밀집형이 아니므로 더 짧았기 때문입니다. 주된 색인의 블록 수는 몇 개인가요?

보조 색인은 일반적으로 주된 색인보다 더 많은 저장 공간과 더 긴 검색 시간이 필요합니다.

그러나 임의의 레코드에 대한 개선된 검색 시간을 제공합니다.

Multilevel Indexes:

다단계 인덱스는 검색 공간을 크게 줄이기 위해 설계되었습니다.

인덱스 블록에서 팬아웃이라고 하는 블록 팩터를 증가시킴으로써 검색합니다.

다단계 인덱스의 첫 번째(기본) 레벨은 인덱스 파일 자체입니다.

두 번째 레벨(중간 레벨)은 첫 번째 레벨의 기본 색인입니다.

세 번째 레벨(현재 가장 높은 레벨)은 두 번째 레벨의 기본 색인입니다.

두 수준의 주요 인덱스 (Two-level Primary Index)입니다.

ISAM (Indexed Sequential Access Method)과 유사한 정적(static) 구조를 가집니다.

더 자세한 내용은 부록을 참조하십시오.

'인덱스 순차 파일' (Indexed Sequential File)은 주문 키 필드에 대한 다중 수준의 주요 인덱스를 가진 순서가 있는 파일입니다.

Dynamic Multilevel Indexes:

동적 다단계 인덱스는 B-트리 및 B+-트리를 사용합니다.

동적으로 조정할 수 있는 구조를 제공하며, 인덱스 삽입 및 삭제 문제를 해결합니다.

"왜 동적인 다중 수준 인덱스인가요?"

ISAM(색인 순차 액세스 방법)은 여전히 인덱스 삽입 및 삭제와 관련된 문제를 겪고 있습니다.

모든 인덱스 수준은 물리적으로 정렬된 파일이며, 이로 인해 삽입 및 삭제에 대한 구조가 변경되지 않습니다.

오버플로우 페이지로 인한 성능 저하 문제가 있습니다.

이러한 제한적인 유연성을 해결하기 위해, 각 인덱스 블록에 새로운 항목을 삽입할 수 있는 공간을 남겨두고 데이터 파일이 커지고 줄어들 때 새로운 인덱스 블록을 생성하거나 삭제하는 데 적절한 삽입/삭제 알고리즘을 사용합니다.

따라서 사람들은 트리 데이터 구조를 기반으로 한 동적 다중 수준 인덱스를 개발했습니다.

Search Trees:

특별한 유형의 트리로, 디스크 파일에 저장된 레코드의 값을 가지고 레코드를 검색하는 데 사용됩니다.

트리 내의 값은 파일의 검색 필드 중 하나의 값입니다.

팬아웃 p (아래 예제에서는 3)을 가진 검색 트리:

각 노드에는 최대 i) p-1개의 검색 값 및 ii) p(노드) 포인터가 포함됩니다.

B+-Tree Structures:

삽입/삭제를 logpN 비용으로 수행할 수 있습니다 (여기서 p = 팬아웃, N = 리프 페이지 수).

트리를 균형있게 유지합니다.

최소 50%의 점유도를 유지합니다 (루트 제외).

각 노드에는 d <= m <= 2d 개의 항목이 포함됩니다. d는 트리의 순서라는 매개변수입니다.

등식 및 범위 검색을 효율적으로 지원합니다.

마지막으로, Index Entries 및 Data Entries에 관한 내용도 포함되어 있습니다:

Index Entries (Direct search):

내부 노드: 검색을 안내합니다.
리프 노드에서의 일부 검색 필드 값은 검색 안내를 위해 반복될 수 있습니다.
내부 노드에는 데이터 레코드가 저장되지 않습니다.

Data Entries (Sequence set):

리프 노드: 데이터 포인터를 저장합니다.
B-트리의 경우 데이터 포인터는 어느 노드에서든 나타날 수 있습니다.
검색 필드의 모든 값에 대한 항목을 가지고 있습니다.
서로 "연결"되어 있습니다 (B 트리와는 반대로).
검색 필드가 키 필드인 경우 레코드로의 데이터 포인터가 있습니다.
검색 필드가 키 필드가 아닌 경우 데이터 파일 레코드를 가리키는 블록 포인터가 있습니다.

B+-Tree Order가 2인 예제:

검색은 루트에서 시작합니다.

키 비교를 통해 검색이 리프 노드로 이동합니다 (ISAM과 유사).

5*, 15를 검색하거나 24 이상의 모든 데이터 엔트리를 검색합니다.

15*를 검색하는 경우, 트리에 없음을 알 수 있습니다!!!

B+-Tree에 인덱스 엔트리 삽입:

올바른 리프 L을 찾습니다.

인덱스 엔트리를 L에 넣습니다.

L에 충분한 공간이 있는 경우 완료!
그렇지 않으면 L을 분할해야 합니다 (L과 새로운 노드 L2로).

항목을 고르게 재분배하고 중간 키를 복사합니다.
L을 가리키는 인덱스 엔트리를 L의 부모 노드에 삽입합니다.

이것은 재귀적으로 발생할 수 있습니다.

인덱스 노드를 분할하려면 항목을 고르게 재분배하고 중간 키를 PUSH UP합니다 (리프 분할과 대조).

분할은 트리를 "성장"시킵니다. 루트 분할은 트리의 높이를 증가시킵니다.

트리의 성장은 위쪽에서 넓어지거나 한 수준 더 높아집니다.

8*를 예제 B+-Tree에 삽입:

최소 점유도가 리프와 인덱스 페이지 분할에서 모두 보장되는 방법을 관찰합니다.

복사 업과 푸시 업의 차이점을 이해하는 것이 중요합니다.

이에 대한 이유를 이해하는 것이 중요합니다.

부모 노드에 삽입될 항목 (5가 복사되었고 리프에 여전히 나타납니다).

루트에서 분할로 인해 높이가 증가한 예제 B+-Tree입니다.

이 예에서는 분배를 통해 분할을 피할 수 있습니다. 평균 점유도가 향상되기 때문입니다.

그러나 실제로는 이렇게 하지 않습니다. 그 이유는 더 많은 I/O 작업을 유발하기 때문입니다!

8*를 루트에서 분할을 사용하여 삽입한 후 예제 B+-Tree의 비교:

8*를 삽입한 후 트리가 어떻게 변하는지 비교합니다.

루트가 분할되어 높이가 증가함을 관찰합니다.

이 분할을 피할 수 있지만 평균 점유도가 향상되도록 항목을 재분배하는 방법입니다. 그러나 이것은 일반적으로 실제로는 수행되지 않습니다. 왜냐하면 I/O가 증가하기 때문입니다!

B+-Tree에서 인덱스 엔트리 삭제:

루트에서 시작하여 해당 항목이 속한 리프 L을 찾습니다.

항목을 삭제합니다.

L이 최소한 반 이상 채워져 있다면 완료됩니다.

L에 항목이 d-1개만 있는 경우,

형제 노드(부모 노드가 동일한 이웃 노드)에서 빌려올 수 있도록 재분배를 시도합니다.

재분배가 실패하면 L과 형제를 병합합니다.

병합이 발생한 경우 L의 부모에서 L 또는 형제를 가리키는 항목을 삭제해야 합니다.

병합은 루트로 전파될 수 있으며 "높이"를 줄입니다. (병합된 노드가 새로운 루트가 됨)

19와 20를 삭제한 후 예제 B+-Tree:

19*를 삭제하는 것은 쉽습니다.

20*를 삭제하는 것은 형제 노드에 항목이 세 개 있으므로 재분배로 수행됩니다.

형제 노드에 있는 24가 20*을 포함한 노드로 이동됩니다.

중간 키가 어떻게 복사되었는지에 주목합니다.

(24라는 이전 가장 왼쪽 검색 키가 27로 대체되었습니다.)

24*를 삭제한 후:

형제 노드에 항목이 두 개만 있기 때문에 재분배할 수 없으므로 병합해야 합니다.

인덱스 항목을 '떨어뜨림' (오른쪽 참조).

인덱스 항목을 '내려뜨림' (아래 참조).

왼쪽 형제 노드와 병합해야 합니다.

분할 키인 17이 자식에게 내려가 새로운 루트가 됩니다.

병합으로 인해 해당 키를 포함하고 있던 이전 루트에서 삭제해야 합니다.

19, 20, 24*를 삭제한 후 예제 B+-Tree:**

실제 B+-Tree에서:

일반적인 오더(차수): 100 (일반적인 채우기 비율: 67%)

오더 = 최소 검색값 (또는 q-1)

평균 팬아웃(p) = 133

일반적인 용량:

높이 4: 133^4 = 312,900,700개의 레코드
높이 3: 133^3 = 2,352,637개의 레코드

대부분의 경우 상위 레벨을 버퍼 풀에 보관할 수 있습니다.

레벨 1 = 1페이지 = 8K바이트
레벨 2 = 133페이지 = 1M바이트
레벨 3 = 17,689페이지 = 133M바이트

요약:

트리 구조 인덱스는 범위 검색에 이상적이며 동등 검색에도 좋습니다.

B+-트리는 동적 구조입니다.

삽입/삭제는 트리 높이를 균형있게 유지하며 logpN 비용이 듭니다.

높은 팬아웃(p)은 깊이가 거의 항상 3 또는 4 미만이라는 의미입니다.

대부분의 경우 정렬된 파일을 유지하는 것보다 훨씬 효율적입니다. (ISAM: 정적 구조

잎 페이지만 수정; 오버플로우 페이지가 필요합니다.

오버플로우 체인은 성능을 저하시킬 수 있습니다.)

옵션 1

K(i) 값이 동일한 중복 인덱스 항목을 각각 레코드마다 포함시킵니다.
이것은 밀도 있는 인덱스일 것입니다.

옵션 2

인덱스 엔트리의 가변 길이 레코드를 사용하고 포인터를 위한 반복 필드를 둡니다.
K(i)에 대한 인덱스 엔트리에 <P(i, 1), ... , P(i, k)> 포인터 목록을 유지합니다.

옵션 3

인덱스 엔트리 자체의 길이를 고정시키고 인덱스 필드 값에 대한 단일 엔트리를 생성하지만 여러 포인터를 처리하기 위해 추가 수준의 간접 참조를 생성합니다.

비밀 색인에 대한 구현 (희소 형태) - 옵션 3 - 예제:

비 키 필드에 대한 인덱스를 구현하는 방법 중 하나입니다.

인덱스 엔트리의 길이를 고정시키고 인덱스 필드 값에 대한 단일 엔트리를 생성합니다.

그러나 여러 포인터를 처리하기 위해 추가 수준의 간접 참조를 사용합니다.

ISAM (Indexed Sequential Access Method):

IBM에 의해 개발된 것으로, 디스크의 실린더 및 트랙과 관련이 깊습니다.

ISAM은 두 수준의 인덱스를 가지며, 정적 구조와 트리 데이터 구조를 가진 인덱스입니다.

각 트리 노드는 디스크 페이지이며 모든 데이터는 리프 페이지에 저장됩니다.

몇몇 리프 페이지에 추가 오버플로우 페이지가 연결됩니다.

ISAM에 대한 주석:

파일 생성: 데이터 페이지는 검색 키에 따라 순차적으로 할당되고 정렬됩니다. 그런 다음 인덱스 페이지가 할당되며 오버플로우 페이지의 공간도 할당됩니다.

인덱스 엔트리: <검색 키 값, 페이지 ID>; 이것들은 데이터 엔트리를 찾는 데 사용되며 이 엔트리들은 리프 페이지에 저장됩니다.

검색: 루트에서 시작하고 키 비교를 사용하여 리프로 이동합니다. 비용은 logFN이며, 여기서 F는 인덱스 페이지당 엔트리 수이고, N은 리프 페이지 수입니다.

삽입: 데이터 엔트리가 속한 리프를 찾아서 거기에 넣습니다.

삭제: 리프에서 찾아 제거하고, 오버플로우 페이지가 비어 있으면 할당 해제합니다.

정적 트리 구조: 삽입/삭제는 리프 페이지에만 영향을 미칩니다.

ISAM 트리 예제:

각 노드는 2개의 항목을 보유할 수 있습니다.

'다음 리프 페이지' 포인터가 필요하지 않습니다. 이유는 무엇일까요?

23*, 48*, 41*, 42를 삽입한 후, 42, 51*, 97*을 삭제한 ISAM 트리의 예제가 나와 있습니다.