> For the complete documentation index, see [llms.txt](https://leehyokyun.gitbook.io/openbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leehyokyun.gitbook.io/openbook/3-3..md).

# 3-3. 데이터베이스 인덱스

데이터베이스 인덱스에 대하여

### 1. Index의 필요성과 Full Table Scan

인덱스가 없는 테이블에서는 책의 첫 페이지부터 마지막 페이지까지 일일이 탐색하는 풀 테이블 스캔(Full Table Scan)이 발생한다. 이는 데이터를 메모리 버퍼에 올려둔 후 차례대로 비교하면서 데이터를 찾아내는 방식이다.

* 색인의 역할: 인덱스는 정렬되어 있는 색인과 같다. 추출하고자 하는 데이터 항목 및 그 순서가 인덱스에 보장되어 있을 때 그 효과가 극대화된다.
* 인덱스 운용 비용: 원본 테이블 데이터의 10% 가량에 해당하는 추가 공간이 필요하며, 데이터 쓰기(CUD) 작업 시 인덱스 재정렬을 위한 추가 연산이 수반된다.
* 설계 고려사항: 공간적 제약, Order By로 인한 File Sort 비용, 추가 데이터를 탐색하기 위한 랜덤 I/O(Random I/O) 비용이 원본 테이블을 순차 I/O(Sequential I/O)로 읽는 비용 대비 얼마만큼의 효용을 가질지 충분한 고려가 필요하다.

### 2. B+Tree 인덱스 구조와 탐색 메커니즘

"보통" 인덱스는 Root Node, Branch Node, Leaf Node로 구성되는 트리 구조를 지닌다(\*각 노드에 모든 데이터를 저장하는 B- Tree, Leaf 노드에만 데이터를 저장하는 B+ Tree 구조가 존재하며, 데이터베이스에서는B+ Tree를 보통 채택).

* 노드별 역할:
  * Root Node와 Branch Node는 하위 노드로 가기 위한 탐색 경로(포인터)를 제공한다.
  * Leaf Node는 실제 데이터가 저장된 위치를 가리키는 주소값(RID 또는 PK,  TID 등)과 인덱스 키 값을 정렬된 상태로 보관한다.
* 탐색 방식: 상위 노드에서 비교 연산을 통해 하위 노드로 이동하며, 최종적으로 Leaf Node에서 일치하는 레코드의 주소를 찾아 원본 테이블에 접근하는 Random I/O(클러스터링 인덱스 루킹)를 수행한다.
  * leaf node에서 가르키는 포인터 정보로 도달하는 탐색과정이 BST의 효율적 탐색, leaf node에서 범위 내에서 정렬된 상태로 서로 이어진(Linked) 탐색 경로의 효율성 극대화(O(1)) 등으로 인해 각 DB table(Heap/Clustered Index)에서 Full table scan하여 발생하는 비용을 상당 부분 줄일 수 있다(탐색 비용 만으로도 I/O 비용 크게 감소).
  * 특히 MySQL(InnoDB)의 경우 데이터까지 보관한 B+겸 B-의 구조이기에 데이터가 존재한다면 바로 탐색하여 꺼내올 수 있다. 참고로, 데이터를 저장/보관한다는 의미는 각 leaf Node의 "페이지"에 저장해야 하는 데이터(PK/raw data)를 적재한다는 것이다(별도의 데이터를 저장한 페이지를 보관하는 것이 아니라, 페이지에 데이터를 저장하는 것임).

### 3. 인덱스  고찰 - BST / B- Tree / B+ Tree

B-/B+ Tree의시작은 BST(Binary Search Tree)로 거슬러 올라간다.

* 단순 BST는 탐색을 logN으로 줄일 수는 있겠으나, 단순히 데이터를 저장하는 개념에서는 올바른 수단은 아니다. 데이터베이스의 데이터 저장 과정은 메모리와 함께, 디스크에서의 page 단위 I/O가 밀접하게 연관하기 때문이다.  (\*BST가 저장할 수 있는 노드의 최대 개수가 2개인 점도 DB 입장에서는 비효율적인 방안)
* 그래서 도입된 방안이 개선된 Tree, 즉 B- Tree이다. 참고로 표준적인 DB의 구조가 B- Tree이지만 내재적으로는 B+ Tree에 가깝다. 가령, leaf에 데이터(포인터)를 저장하는 구조인 B+ Tree 이지만, 따지고 보면 모든 Branch Node에 node key 정렬 및 범위 정보(rowId/TID 등)를 저장하는 B- Tree 구조이다.

  (\*유의할 점, 데이터를 저장한 페이지를 적재하는 것이 아니라, 각 노드의 페이지에 가능한 만큼의 데이터를 적재하는 구조이다.)

B- Tree는 기본적으로 1개의 node가 아닌, 여러 node를 가지는 것, 그리고 각 branch node가 데이터를 보유한다는 것이 핵심이다.

* 여러 key를 보유하는 각 노드와, 그 노드에서 뻗어가는 자식 노드 역시 2개가 아닌 여러 개로 갈라진다.
* 자식 노드는 부모가 가진 key에 의해 군집화되어 위치해있으며, 데이터 규모가 1억건을 넘겨도 트리의 높이가 낮다. 물론 해당 key값이 위와 같이 범위를 나타내는 포인터가 될 수 있고, 혹은 실제 “데이터”가 될 수도 있다. key + data를 보유한 구조를 internal Node 구조라 하며, 원하는 데이터를 포함한다면 즉시적인 탐색이 가능한 것.

B+ Tree는 B- Tree 구조에서, 실제 데이터는 반드시 최하단 leaf node에만 존재한다는 규칙이 존재한다.

* 즉, 각 노드는 이분 탐색을 위한 key(routing) 정보만 보유하며, 실제 데이터(포인터)는 최하단에 존재한다. 
* 이때각 leaf Node는 모두 연결되어있다. 따라서 범위 탐색 후 leaf를 따라 가기만 하면 된다. 따라서 List의 탐색이 O(1)의 시간복잡도를 가지는 것처럼(idx기반) 원하는 데이터를 금방 탐색할 수 있다.
* 다만 각 세부 형태는 DB마다 조금씩 다른데,

  \- Oracle의 경우 rowId(포인터)를 보유(일반 테이블은 Heap형태로 저장, 인덱스가 table block row 위치를 가르킴)

  \- PostgreSQL의 경우 tuple에 다음 internode 및 heap table block / 내부의 tuple offset을 가르키는 TID 정보 존재.

  \- MySQL(InnoDB)의 경우 DB table 구조는 Index 그 자체(Clustered), leaf node의 page에 실제 데이터 저장.

### 4. Fan-out 효과와 디스크 I/O 최적화

B-Tree 인덱스에서 Fan-out이란 하나의 노드가 가질 수 있는 자식 노드의 최대 개수, 즉 분기 계수를 의미하며 디스크 I/O 효율을 결정하는 핵심적인 아키텍처 요소이다.

* 트리 깊이(Depth) 제한: Fan-out 값이 커질수록 한 번에 탐색할 수 있는 경로가 넓어지므로 트리의 전체 깊이(Depth)가 얕아진다. 대규모 데이터셋 환경에서도 대개 3\~4단계의 깊이만으로 수억 건의 데이터를 탐색할 수 있는 기반이 된다.
* 디스크 I/O 비용 감소: 데이터 탐색 시 트리의 깊이가 깊을수록 더 많은 노드를 거쳐야 하므로 디스크 블록을 읽는 I/O 횟수가 늘어난다. Fan-out을 극대화하여 깊이를 최소화하는 것은 Random I/O 성능을 극적으로 향상시키는 결정적인 요인이다.
* 페이지 크기와 Fan-out의 관계: 한 페이지(예: InnoDB 16KB) 내에 인덱스 키 값과 포인터를 최대한 많이 담을 수 있을 때 Fan-out이 증가한다. 따라서 인덱스 키 값의 크기를 단순하고 작게 유지(대리키 활용 등)해야만 한 페이지에 더 많은 이정표를 채워 넣을 수 있어 Fan-out 효과를 최대로 누릴 수 있다.

### 5. 복합 인덱스(Composite Index) 구성 원리

두 개 이상의 컬럼을 묶어서 구성하는 복합 인덱스는 컬럼의 배치 순서가 탐색 성능을 결정하는 핵심 요인이다.

* 선행 컬럼의 중요성: 복합 인덱스는 첫 번째 지정된 선행 컬럼을 기준으로 먼저 정렬되고, 선행 컬럼의 값이 같을 때에만 두 번째 컬럼 기준으로 정렬된다.
* 스캔 범위 최적화: 동등 조건(=)이면서 카디널리티(선택도)가 높은 컬럼을 인덱스 앞쪽에 배치해야 스캔해야 할 범위 자체를 효과적으로 줄일 수 있다.
* 접두어 규칙 위배 시 효과: 인덱스 내 순서(접두) 위치가 조건절과 동일하지 않다면 인덱스를 효율적으로 타지 못해 Random I/O 비용이 대폭 증가한다. 이 경우 차라리 Full Table Scan을 통한 순차 I/O 비용이 더 유리할 수 있다.

### 6. 커버링 인덱스(Covering Index)를 통한 Random I/O 제거

쿼리를 충족시키기 위한 모든 컬럼이 인덱스 자체에 포함되어 있어, 원본 테이블 블록을 전혀 방문할 필요가 없는 인덱스 탐색 방식이다.

* 이차 탐색 비용: 일반적인 인덱스 검색은 Leaf Node에서 키 값을 획득한 후 Clustered Index Look up이 추가적으로 발생한다.
* 성능 최적화: 커버링 인덱스가 적용되면 Leaf Node에 있는 인덱스 데이터만으로 쿼리 결과를 모두 반환할 수 있으므로, 테이블 추가 방문에 따른 무거운 Random I/O 비용을 완전히 제거하여 성능을 극대화한다.

### 7. DB 엔진별 인덱스 동작 메커니즘 차이 비교

데이터베이스 엔진의 설계 사상에 따라 인덱스의 저장 방식과 탐색구조가 완전히 다르며, 이는 조회 성능 중심인가 또는 데이터 저장/연산 중심인가에 따른 전략적 차이에서 비롯된다.

* MySQL InnoDB (조회 성능 중심 아키텍처):
  * 클러스터링 인덱스(Clustered Index) 구조를 채택하여, 기본키(PK) 인덱스의 Leaf Node에 실제 테이블의 로우 데이터가 정렬된 상태로 직접 저장된다.
  * 세컨더리 인덱스(Secondary Index)는 Leaf Node에 실제 물리 주소가 아닌 PK 값을 논리적 포인터로 가진다. 이로 인해 세컨더리 인덱스로 검색 시 PK 인덱스를 한 번 더 타야 하는 이차 탐색 비용이 존재한다.
  * 하지만 인덱스 자체에 데이터가 묶여 정렬되어 있으므로, 특정 키 범위나 PK 기반 조회 시 데이터의 지역성(Locality)이 극대화되어 읽기 및 조회 성능에서 압도적인 우위를 점한다.
* Oracle / PostgreSQL (데이터 저장 및 연산 중심 아키텍처):
  * 테이블 데이터는 순서 없이 빈 공간에 자유롭게 저장되는 힙 구조(Heap Table)에 보관되며, 인덱스는 데이터의 실제 물리적 위치 주소(RID / Tuple ID)만을 가리키는 포인터 역할을 수행한다.
  * 데이터가 수정되거나 삽입될 때 인덱스 트리 전체를 물리적으로 재정렬하고 데이터를 이동시키는 부하가 적어, 쓰기 및 데이터 저장/연산 자체를 매우 빠르고 효율적으로 처리한다.
  * 인덱스가 단순 포인터 구조이기 때문에 세컨더리 인덱스를 타더라도 추가적인 PK 인덱스 룩업 과정 없이 바로 힙 영역의 주소로 접근할 수 있으나, MySQL처럼 데이터 자체가 정렬되어 묶여있는 구조에 비해서는 연속된 범위 조회 시 읽기 효율성과 캐시 이점을 극대화하기 어렵다.

### 8. Unique Key와 Foreign Key의 자동 인덱스 생성 목적

데이터베이스 시스템에서 Unique 제약조건(UQ)이나 외래키 제약조건(FK)을 설정하면 인덱스가 자동으로 생성된다. 이는 단순히 선택도가 높아 성능을 향상시키기 위한 부수적 효과가 아니다.

* 중복 검증(Unique 무결성): 데이터가 새로 삽입되거나 수정될 때, UQ의 중복 유무를 확인해야 한다. 인덱스가 없다면 매번 Full Table Scan으로 전체 행을 검사해야 하므로, 인덱스 기반의 빠른 중복 검증을 수행하기 위해 필수적이다.
* 참조 무결성 검증: 부모-자식 테이블 간의 데이터 정합성을 유지하기 위해 조회 및 쓰기 시 외래키를 기준으로 한 연산과 탐색이 수반되므로 빠른 참조 무결성 검증이 필요하다. 이는 연산 처리가 많이 발생하거나 해당 기준에 의거한 탐색이 많이 발생할 것으로 예상한 MySQL의 전략적인 선택이다.
* JOIN 연산 최적화: 조인 연산 처리 시 일반적으로 자식 테이블 스캔 후 부모 테이블 스캔 순으로 이어지며, FK 인덱스가 존재한다면 부모 테이블을 스캔하기 위한 PK 확보 및 PK Look up이 즉시 가능해진다. 만약 FK 인덱스가 존재하지 않는다면, 자식 테이블에서 찾은 FK를 부모 테이블에서 찾기 위해 매번 Full Table Scan을 유발하게 된다.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://leehyokyun.gitbook.io/openbook/3-3..md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.