DBMS-인덱싱

우리는 데이터가 기록의 형태로 저장된다는 것을 알고 있습니다. 모든 레코드에는 고유하게 인식하는 데 도움이되는 키 필드가 있습니다.

인덱싱은 인덱싱이 수행 된 일부 속성을 기반으로 데이터베이스 파일에서 레코드를 효율적으로 검색하는 데이터 구조 기술입니다. 데이터베이스 시스템의 인덱싱은 책에서 보는 것과 유사합니다.

인덱싱은 인덱싱 속성을 기반으로 정의됩니다. 인덱싱은 다음과 같은 유형이 될 수 있습니다.

Primary Index− 기본 인덱스는 정렬 된 데이터 파일에 정의됩니다. 데이터 파일은key field. 키 필드는 일반적으로 관계의 기본 키입니다.
Secondary Index − 보조 인덱스는 후보 키이고 모든 레코드에서 고유 한 값을 갖는 필드 또는 중복 값이있는 키가 아닌 필드에서 생성 될 수 있습니다.
Clustering Index− 클러스터링 인덱스는 정렬 된 데이터 파일에 정의됩니다. 데이터 파일은 키가 아닌 필드에서 정렬됩니다.

Ordered Indexing은 두 가지 유형이 있습니다-

고밀도 색인
희소 색인

고밀도 색인

고밀도 인덱스에는 데이터베이스의 모든 검색 키 값에 대한 인덱스 레코드가 있습니다. 이렇게하면 검색 속도가 빨라지지만 인덱스 레코드 자체를 저장하는 데 더 많은 공간이 필요합니다. 인덱스 레코드에는 검색 키 값과 디스크의 실제 레코드에 대한 포인터가 포함됩니다.

희소 색인

희소 인덱스에서는 모든 검색 키에 대해 인덱스 레코드가 생성되지 않습니다. 여기의 인덱스 레코드에는 검색 키와 디스크의 데이터에 대한 실제 포인터가 포함됩니다. 레코드를 검색하려면 먼저 인덱스 레코드로 진행하고 데이터의 실제 위치에 도달합니다. 찾고있는 데이터가 인덱스를 따라 직접 도달하지 않는 경우 시스템은 원하는 데이터를 찾을 때까지 순차 검색을 시작합니다.

다단계 색인

인덱스 레코드는 검색 키 값과 데이터 포인터로 구성됩니다. 다단계 인덱스는 실제 데이터베이스 파일과 함께 디스크에 저장됩니다. 데이터베이스 크기가 커짐에 따라 인덱스 크기도 커집니다. 검색 작업의 속도를 높이기 위해 인덱스 레코드를 주 메모리에 보관해야하는 엄청난 필요성이 있습니다. 단일 레벨 인덱스를 사용하면 대용량 인덱스를 메모리에 보관할 수 없으므로 여러 디스크 액세스가 발생합니다.

Multi-level Index는 인덱스를 여러 개의 작은 인덱스로 분할하여 가장 바깥 쪽 레벨을 너무 작아서 메인 메모리의 어느 곳에서나 쉽게 수용 할 수있는 단일 디스크 블록에 저장할 수 있도록합니다.

B ⁺ 나무

AB ⁺ 트리는 다중 레벨 인덱스 형식을 따르는 균형 이진 검색 트리입니다. B ⁺ 트리 의 리프 노드 는 실제 데이터 포인터를 나타냅니다. B ⁺ 트리는 모든 리프 노드가 동일한 높이로 유지되도록하여 균형을 유지합니다. 또한 리프 노드는 링크 목록을 사용하여 연결됩니다. 따라서 B ⁺ 트리는 순차 액세스뿐 아니라 임의 액세스도 지원할 수 있습니다.

B ⁺ Tree의 구조

모든 리프 노드는 루트 노드에서 동일한 거리에 있습니다. AB ⁺ 나무는 순서입니다n 어디 n모든 B ⁺ 트리에 대해 고정됩니다 .

Internal nodes −

내부 (비 리프) 노드에는 루트 노드를 제외하고 최소한 ⌈n / 2⌉ 포인터가 포함됩니다.
기껏해야 내부 노드에는 n 포인터.

Leaf nodes −

리프 노드는 최소한 ⌈n / 2⌉ 레코드 포인터와 ⌈n / 2⌉ 키 값을 포함합니다.
최대 리프 노드는 다음을 포함 할 수 있습니다. n 레코드 포인터 및 n 키 값.
모든 리프 노드에는 하나의 블록 포인터가 있습니다. P 다음 리프 노드를 가리키고 연결 목록을 형성합니다.

B ⁺ 트리 삽입

B ⁺ 트리는 바닥에서 채워지고 각 항목은 리프 노드에서 수행됩니다.
리프 노드가 오버플로되면-
- 노드를 두 부분으로 분할합니다.
- 파티션 i = ⌊(m+1)_/2⌋.
- 먼저 i 항목은 하나의 노드에 저장됩니다.
- 나머지 항목 (i + 1 이후)은 새 노드로 이동됩니다.
- i^th 키는 리프의 부모에 복제됩니다.
리프가 아닌 노드가 오버플로되면-
- 노드를 두 부분으로 분할합니다.
- 노드 분할 i = ⌈(m+1)_/2⌉.
- 최대 항목 i 하나의 노드에 보관됩니다.
- 나머지 항목은 새 노드로 이동됩니다.