인덱싱 (1) - 순서 인덱스

인덱싱이란?

📚 데이터베이스의 색인 = 인덱스!

• 책에서 특정 단어를 찾을 때 색인을 통해 해당 페이지를 빠르게 조회하듯,

  DB도 인덱스를 통해 필요한 레코드가 있는 디스크 블록을 찾아감

• 인덱스는 정렬된 상태로 저장되며, 전체 데이터보다 훨씬 작음

📌 인덱스가 필요한 이유

• 인덱스 없이는 모든 쿼리가 전체 테이블을 순회해야 하므로, 몇 개의 레코드만 필요할 때 매우 비효율적임
• 예) takes 테이블에서 한 학생의 수강 정보만 조회할 때도 전체 테이블을 읽게 됨

🛠️ 인덱스 구현의 어려움

• 학생 ID 기준으로 정렬된 인덱스를 유지한다고 해도:
  1. 대용량 DB에서는 인덱스 자체도 매우 커짐
  2. 정렬 유지 비용이 큼
  3. 삽입/삭제 시 인덱스 갱신 비용이 큼
• 따라서 DBMS는 더 정교한 인덱싱 기법을 사용함

인덱스의 종류

인덱스에서는 기본적으로 두 가지 종류가 있다.

인덱싱 기법 평가 기준

몇 가지 순서 인덱스를 다루기에 앞서서, 인덱싱 기법을 평가하는 기법을 알아보자.

→ 일반적으로 성능 향상을 위해 공간을 조금 희생하는 것이 바람직함

검색 키

• 인덱스를 통해 레코드를 조회할 때 사용하는 속성 또는 속성 집합을 의미함

• 여기서 말하는 검색 키는 primary key나 superkey와는 다른 개념임.

  • 즉, 유일할 필요는 없음

• 한 파일에 여러 개의 인덱스를 둘 수 있으므로, 검색 키도 여러 개일 수 있음

  예) 책을 제목, 저자, 주제로 검색

순서 인덱스란?

• 특정 검색 키 기준으로 정렬된 순서대로 저장된 인덱스 구조임
• 마치 책의 색인처럼, 각 키 값에 대해 관련된 레코드들을 빠르게 찾을 수 있음
• 이를 통해 빠른 랜덤 접근이 가능함

순서 인덱스의 종류

• 실제 레코드들이 저장된 파일도 어떤 속성 기준으로 정렬될 수 있음.
• 하나의 파일에는 여러 인덱스(서로 다른 search key 기준)를 가질 수 있음

이제부터 여러 가지 순서 인덱스 다룰 예정!

순서 인덱스를 다루기 위해 등장하는 예시 파일들의 경우, 어떠한 검색 키에 의해 연속적인 순서로 정렬됨.

이를 인덱스 순차 파일(Index-Sequential File) 이라고 함.

1. 밀집 인덱스 vs 희소 인덱스

인덱스에는 인덱스 항목(index entry)이라는 것이 존재한다.

인덱스 항목? 인덱스에 저장된 한 줄의 정보를 말함. 기본적으로 다음 두 가지를 포함함:

1. Search key 값 → 인덱싱 대상이 되는 속성 값 (예: ID = 22222)
2. 포인터(pointer) → 해당 search key 값을 가진 레코드(또는 레코드들의 시작 위치)를 가리키는 주소 → 보통 “디스크 블록 번호 + 오프셋(offset)”으로 구성됨

우리는 이 인덱스 항목의 개수와 범위에 따라 순서 인덱스를 구분할 수 있다.

📌 사용 예시 1: ID가 Primary Key인 경우

• Dense Index 사용 시: ID = 22222인 교수의 레코드에 바로 접근 가능
• Sparse Index 사용 시: ID = 22222가 없다면, 가장 가까운 작은 키(10101)에서 시작해 순차 검색

🧠 사전(dictionary)을 예로 들면, 각 페이지 상단 단어가 sparse index 역할을 함

📌 사용 예시 2: Search key가 Primary key가 아닌 경우

• dept_name을 search key로 설정하여 dense clustering index 생성 가능
• 단, instructor 파일이 dept_name 기준으로 정렬되어 있어야 함 (clustering index 조건 충족)
• ex. “History” 레코드를 찾고 싶다면:
  1. 첫 번째 History 교수 레코드에 접근
  2. 이후 레코드들을 차례대로 순차 탐색

✅ 밀집 vs 희소 : 실용적인 절충안

• 블록마다 1개 인덱스 항목만 두는 희소 인덱스가 타협점임
  • 디스크에서 블록 단위 접근 비용이 가장 크기 때문
  • 한 블록을 메모리에 로드하면, 블록 내 순차 검색 비용은 매우 작음
• 단, 동일한 search-key 값이 여러 블록에 분산된 경우도 고려 필요
  • 이를 위한 보완 구조는 설계에 따라 조정 가능

2. 단일 인덱스 vs 다계층 인덱스

• 단일 인덱스 - 인덱스가 1개만 존재하는 경우
• 다단계 인덱스 - 인덱스가 여러 개 존재하며, 서로 간의 관계가 있는 경우

단일 인덱스의 한계

ex. 1,000,000개의 레코드에 대해 dense index를 만든다고 하자.

하나의 블록에 100개의 인덱스 항목이 들어간다고 가정 시 총 10,000개의 블록이 필요함

레코드가 1억 개라면? 인덱스는 **1,000,000 블록 (약 4GB)**로 커짐

• 전체 인덱스를 메모리에 유지하기 어려움

이 경우, 디스크에서 여러 블록을 읽으며 검색해야 함.

• 이진 탐색을 쓴다고 해도 b개의 블록이 있을 때 최대 \log_{2}(b) 개의 블록에 접근해야 함.

그래서, 다단계 인덱스가 필요한 것!

다단계 인덱스의 구조

• inner index: 10,000 블록 → outer index: 100 블록
• outer index가 메모리에 올라와 있다면, 검색 시 index 블록 1개만 접근하면 됨
• 기존 이진 탐색 대비 최대 14배 더 많은 검색 처리 가능

다단계 인덱스의 장점

순서 인덱스의 관리

인덱스의 업데이트

인덱스의 형태와 관계없이, 레코드가 파일에 삽입되거나 삭제될 때마다 인덱스도 반드시 갱신해야 함.

또한 레코드가 수정되는 경우, 검색 키(search-key) 속성이 바뀐다면 해당 인덱스도 수정되어야 함.

📌 예: instructor 테이블에서 dept_name이 수정되면, dept_name 속성 기반 인덱스도 갱신해야 함.

인덱스의 업데이트는 삽입(insertion) 과 삭제(deletion)만 고려하면 충분함.

왜? 레코드 수정(update) 은 내부적으로 기존 레코드 삭제 → 새로운 레코드 삽입으로 간주.

인덱스의 업데이트 - 삽입

레코드 삽입 시 시스템은 해당 레코드의 검색 키 값을 사용하여 인덱스를 조회한 후, 다음과 같이 처리함:

✅ Dense Index (조밀 인덱스)인 경우

1. 🔍 검색 키 값이 인덱스에 존재하지 않으면: 해당 키 값을 적절한 위치에 삽입함.
2. 🔍 이미 존재하는 경우:

• 모든 동일 키 레코드의 포인터를 저장하는 인덱스라면 : 새 레코드의 포인터를 추가함.
• 첫 번째 레코드만 가리키는 경우 : 새 레코드를 동일 키 값을 가진 기존 레코드들 뒤에 배치함.

✅ Sparse Index (희소 인덱스)인 경우

• 일반적으로 각 블록에 대해 하나의 인덱스 항목만 저장함.
• 새 블록이 만들어지는 경우: 해당 블록에서 가장 첫 번째 검색 키 값을 인덱스에 삽입함.
• 기존 블록에 새 레코드 삽입 시:
  • 삽입된 레코드가 블록 내 최소 검색 키라면 인덱스를 갱신함.
  • 그렇지 않다면 인덱스 변경은 불필요함.

인덱스의 업데이트 - 삭제

삭제 시 시스템은 먼저 해당 레코드를 검색한 뒤, 다음과 같이 처리함:

✅ Dense Index (조밀 인덱스)인 경우

1. 🔍 해당 검색 키 값을 가진 레코드가 하나뿐인 경우: 인덱스 항목 자체를 삭제함.
2. 🔍 여러 레코드가 동일 키 값을 가진 경우:

• 모든 레코드의 포인터를 저장하는 인덱스라면 해당 레코드의 포인터만 삭제함.
• 첫 번째 레코드만 가리키는 경우삭제된 레코드가 첫 번째였다면 인덱스 포인터를 다음 레코드로 갱신함.

✅ Sparse Index (희소 인덱스)인 경우

1. 🔍 검색 키 값이 인덱스에 없는 경우: 인덱스 갱신 필요 없음.
2. 🔍 인덱스에 검색 키 값이 존재할 경우

• 해당 키 값을 가진 레코드가 하나뿐이라면 다음 검색 키 값을 새 인덱스로 대체함
  • 만약 이미 존재하는 키라면, 중복 방지를 위해 기존 인덱스를 삭제함.
• 해당 인덱스가 삭제된 레코드를 가리키고 있다면, 인덱스 포인터를 다음 레코드로 갱신함.

다계층 인덱스의 업데이트

다계층 인덱스(multilevel index)의 경우, 가장 하위 인덱스(leaf level) 에서 먼저 삽입 또는 삭제를 수행하고, 그에 따라 상위 인덱스들도 갱신함.

• 각 상위 인덱스는 하위 인덱스를 단순한 파일로 간주하므로, 하위 인덱스의 변경은 상위 인덱스 갱신을 유발함.
• 이 과정은 최상위 인덱스까지 반복됨.

보조 인덱스

보조 인덱스 : 클러스터링 인덱스(clustering index)와 달리, 인덱스의 search key가 파일의 저장 순서와 동일하지 않고, 다른 속성을 기준으로 생성된 인덱스.

🔍 보조 인덱스의 기본 성질

보조 인덱스는 항상 Dense Index여야 함.

• 따라서, 모든 검색 키 값에 대해 각 레코드로 가는 포인터가 반드시 있어야 함.

반면, 클러스터링 인덱스(clustering index)는 sparse index일 수 있음.

• 파일 내 연속된 영역에서 키 값을 찾아갈 수 있기 때문임.

🧱 보조 인덱스와 클러스터링 인덱스의 차이

보조 인덱스와 클러스터링 인덱스가 같은 검색 키(candidate key) 를 쓴다면, 구조는 유사함.

• 하지만 보조 인덱스는 레코드들이 물리적으로 순차 저장되어 있지 않음.
• 클러스터링 인덱스가 candidate key가 아닌 경우: 특정 키 값에 대한 첫 번째 레코드만 가리키면 됨.
• 보조 인덱스가 candidate key가 아닌 경우: 해당 키를 가진 모든 레코드를 찾기 위해 모든 레코드에 대한 포인터가 필요함.

🔁 중복 키를 갖는 보조 인덱스의 구현

중복 키(nonunique search key)를 위한 보조 인덱스 구현 방식:

• 인덱스가 직접 레코드를 가리키는 것이 아니라, 버킷(bucket) 을 가리킴. 각 버킷은 다시 여러 레코드 포인터들을 담고 있음.
• 아래의 그림이 대표적인 예시

그러나 이러한 방법에는 여러가지 단점이 존재한다.

1. 간접 접근으로 인해 성능 저하 발생 : 인덱스 → 버킷 → 레코드 접근으로 추가 I/O 필요
2. 공간 낭비 : 키가 거의 중복되지 않는 경우, 하나의 버킷이 거의 비어 있게 되어 메모리 낭비 발생

🏃‍♂️ 순차 접근과 성능 문제

• 클러스터링 인덱스는 물리적으로 레코드가 키 순서로 정렬되어 있기 때문에 순차 접근이 효율적임.
• 반면 보조 인덱스는 정렬 기준이 다름:
  • 보조 인덱스 기준으로 순차 접근 시, 레코드 하나마다 새로운 블록을 읽어야 해서 느림.

🛠️ 수정 작업 시 보조 인덱스의 갱신

• 삽입/삭제 시 보조 인덱스도 dense index처럼 갱신해야 함.
• 하나의 파일에 여러 인덱스가 존재할 경우:
  • 파일이 수정되면 모든 인덱스를 갱신해야 함.

⚖️ 설계자의 선택

• 보조 인덱스는 클러스터링 인덱스가 아닌 키로 질의할 때 성능 향상을 가져옴.
• 하지만, 수정 비용이 높음.
• 따라서 설계자는 질의 빈도 vs 수정 빈도를 고려해 보조 인덱스의 생성 여부를 결정해야 함.

다중 키에 대한 인덱스

📌 복합 검색 키

• 하나의 속성이 아닌 여러 속성으로 구성된 검색 키를 **복합 검색 키(composite search key)**라 부름.
• 예: (a₁, a₂, ..., aₙ) 형태로 구성되며, 각각 A₁, A₂, ..., Aₙ 속성에 해당함.

🧱 인덱스 구조

• 구조 자체는 단일 키 인덱스와 동일함.
• 차이점은 **검색 키(search key)**가 단일 속성이 아니라 속성들의 튜플이라는 점임.

🔤 정렬 방식 - 사전식 정렬

• 복합 키는 사전식 순서로 정렬됨.
• 두 개의 복합 키 (a₁, a₂)와 (b₁, b₂) 비교 시:
  • a₁ < b₁이면 (a₁, a₂) < (b₁, b₂)
  • 또는 a₁ = b₁이고 a₂ < b₂이면 역시 (a₁, a₂) < (b₁, b₂)

📚 예시

• takes 릴레이션에서 (course_id, semester, year)를 키로 하는 인덱스를 고려할 수 있음.
• 이 인덱스를 통해 특정 학기와 연도에 특정 과목을 수강한 학생들을 효율적으로 조회 가능함.

💡 활용

• 정렬된 복합 키 인덱스는 단지 하나의 질의에만 유용한 것이 아님.
• 다양한 질의 유형에 대해서도 효율적인 탐색이 가능함