[DATABASE] 인덱스란?

Real MySQL 8.0 책과 유튜브 [쉬운 코드]님의 데이터베이스 강의를 참고하여 작성하였습니다.

---

1. 인덱스란

데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다. 데이터베이스에서 검색, 정렬 및 필터링 작업을 빠르게 수행하는데 도움을 주며, 특정 열에 대한 검색을 최적화하는 역할을 한다. 인덱스는 책의 찾아보기(index, 색인)와 같이 내용을 바로 찾을 수 있도록 지원한다. 사전순으로 키워드별로 나열이 되어 있고, 키워드 옆에는 해당 키워드가 담겨있는 책의 페이지를 가리키는 것처럼 데이터베이스의 인덱스 테이블에서도 데이터 칼럼과 실제 메모리 상의 주소 위치를 담고 있다. 

 

SELECT * FROM user WHERE id = "mysterlee";

테이블에서 위의 조건을 만족하는 데이터를 찾는 과정을 생각해보자.

인덱스 테이블이 없다면 순차적 접근(Full Table Scan)으로 탐색해야 한다. 해당 데이터가 마지막에 있을 경우 전체를 다 탐색해야 한다. 비효율적이다. 하지만 last_name을 인덱스로 하는 테이블을 가지고 있다면 O(logN)의 시간 복잡도로 빠르게 탐색하여 데이터를 가져올 수 있다. 어떻게 빠르게 데이터를 탐색할 수 있는지는 밑에서 이야기해 보도록 하겠다.

2. 인덱스는 왜 필요할까?

인덱스의 장점

▶ 데이터 검색 속도 향상

인덱스는 특정 열을 검색할 때 데이터베이스에서 더 빠르게 원하는 데이터를 찾을 수 있도록 도와준다. 인덱스를 사용하면 전체 테이블을 스캔하는 대신 인덱스 키를 검색하여 데이터 위치를 찾을 수 있다.

 

▶ 데이터 정렬 속도 향상

데이터베이스에서 정렬된 결과를 반환해야 하는 경우 이미 정렬이 되어 있기 때문에 인덱스를 사용하면 데이터를 더 빠르게 정렬하고 반환할 수 있다.

 

▶ 조인 성능 향상

두 개 이상의 테이블을 조인할 때, 인덱스를 사용하면 데이터베이스가 관련 행을 빠르게 찾고 병합할 수 있기  때문에 조인 성능이 향상된다.

 

▶ 쿼리 성능 최적화

데이터베이스 쿼리의 성능을 최적화하여 사용자 경험을 향상시킬 수 있다. 데이터베이스 인덱스를 올바르게 설계함으로써 쿼리의 실행 속도를 높일 수 있다.

 

인덱스의 단점

▶ 추가적인 공간필요

인덱스는 데이터베이스 내에서 자체 인덱스 테이블을 생성하므로 추가적인 공간을 필요로 한다.(보통 DB크기의 10% 정도의 추가 공간 필요)

 

▶ 인덱스 유지관리 비용

인덱스 테이블은 이진트리 검색을 사용하고 정렬이 되어있기 때문에 인덱스에 대한 필드 삽입, 수정, 삭제가 빈번할 경우, 인덱스 테이블 또한 재정렬이 필요하여  전체적인 성능저하가 발생할 수 있다.

• 정렬된 상태를 계속해서 유지시켜줘야 한다.
• Index 테이블, 원본 테이블 모두 최신 상태를 유지해야 하므로 유지 비용이 증가한다.

 

▶ 인덱스가 모든 쿼리에 도움을 주지 않음

인덱스는 특정 유형의 쿼리에 도움을 주지만 모든 쿼리에 도움을 주지는 않는다. 일부 쿼리에서는 인덱스를 사용하지 않는 것이 빠를 수 있다.

 

Full Scan이 더 좋은 경우

• table의 데이터의 개수가 적을 때
• 조회하려는 데이터가 테이블의 상당 부분을 차지할 때

언제 인덱스를 적용할까?

• 데이터가 충분히 많을 경우
• NULL 값이 없는 칼럼
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 칼럼
• WHERE 조건절, JOIN, ORDER BY가 자주 사용되는 칼럼
• Covering Index
• 카디널리티가 높은 칼럼
  • 카디널리티가 높다: 중복되는 데이터가 적다

※ Covering Index : 조회하려는 attribute(s)를 인덱스가 모두 가지고 있을 때 조회 성능이 빠르다.

인덱스 생성 전략

• WHERE 절에서 사용되는 열에 생성(WHERE절에 사용되는 열이라도 자주 사용해야 가치가 있다.)
• 데이터 중복도가 낮은 열에 생성
• JOIN에 자주 사용되는 열에 생성
• 사용하지 않는 인덱스는 제거
• 삽입/수정/삭제가 늦더라도 빨리 읽기를 선택하는 것 또한 하나의 전략이다.

3. 인덱스의 종류

인덱스의 종류에는 PK를 기준으로 하나의 테이블에 하나만 생성되는 클러스터 인덱스, 후보키를 활용한 넌 클러스터 인덱스(보조인덱스)가 있다. 여기서 '클러스터'의 정의를 짚고 넘어가자. 클러스터는 연관 관계가 있는 것들이 무리를 이루는 것을 말한다. 이는 클러스터 인덱스의 특징과도 같다. 테이블에서는 데이터가 유사한 것들끼리 묶여 저장되는데, 비슷한 데이터들이 동시에 선택될 때 빛을 발한다.

 

	Clustered Index	Non-Clustered Index
검색 속도	빠름	느림
탐색 방법	인덱스 검색 -> 리프페이지(실제 데이터 위치) 이동	인덱스 검색 -> 리프페이지 -> 데이터 페이지(실제 데이터 위치)로 이동
입력, 수정, 삭제 속도	느림	빠름
메모리 사용량	적음	많음
인덱스 생성	테이블 당 하나	여러개의 non-clustered index 생성 가능
포인터	블럭 단위(페이지)의 포인터	페이지에 대한 포인터 + 실제 행에 대한 포인터
리프노드	실제 데이터	실제 데이터를 가리키는 포인터
정렬	테이블 레코드가 인덱스와 일치하도록 물리적 재정렬	인덱스의 정렬과 실제 데이터의 정렬은 관련 없음
Key	기본키(Primary Key)	후보키(Candidate Key) 유일성과 최소성을 만족

클러스터 인덱스와 논 클러스터 인덱스 구조에서 큰 차이는 리프 레벨에서 나타난다. 클러스터 인덱스의 경우 리프 노드가 실제 데이터 페이지를 가리키지만, 논 클러스터 인덱스의 경우 실제 데이터 페이지에 대한 정보와 오프셋(페이지 내 순서)에 대한 정보를 포함하고 있다. 클러스터 인덱스의 특성상 항상 정렬된 상태를 유지하고 있기 때문에 오프셋에 대한 정보가 필요 없지만, 논클러스터 인덱스에서 실제 데이터 테이블은 정렬되어 있지 않기 때문에 오프셋 정보를 필요로 한다. 자세한 비교는 아래에서 더 살펴보자.

▷ 클러스터 인덱스(Clustered Index)

• 데이터들을 일정 기준으로 정렬해 주는 인덱스(PK 값에 의해 정렬) - PK에 대한 의존도가 크므로 PK를 신중히 결정해야 함.
• PK의 변경은 데이터의 물리적인 저장 위치 또한 변경
• 데이터 삽입, 수정, 삭제 시에 항상 정렬된 상태를 유지
• PK 값에 의해 레코드의 저장 위치가 결정
• 테이블 당 하나의 클러스터 인덱스만 생성가능 - 테이블이 한 개
• 클러스터 인덱스의 리프노드에는 레코드의 모든 칼럼이 같이 저장
• 클러스터 인덱스 자동 생성 우선순위(MySQL 기준)
  
  1. PK로 지정한 칼럼
  2. UNIQUE이고  NOT NULL로 지정한 칼럼 중 첫 번째
  3. 내부적으로 AUTO_INCREMENT가 적용된 칼럼을 만들어서 해당 컬럼을 클러스터 인덱스의 기준 칼럼으로 설정
     • 내부적으로 추가되는 PK는 사용자에게 노출되지 않고, 쿼리문장에도 사용할 수 없다. 
     • 즉, 이러한 클러스터 인덱스는 활용할 때 아무런 도움을 받지 못하기에, PK 값을 추가하여 잘 활용될 수 있도록 하자. 

▷ 논-클러스터 인덱스(Non-Clustered Index)

• 보조 인덱스(Secondary Index)라고도 함
• 개념적으로 후보키(UNIQUE)에만 부여 가능한 인덱스
• 테이블 당 여러 개의 인덱스 생성 가능
• 실제 주소를 참조하고 있는 클러스터형 인덱스보다 검색속도는 느리지만 데이터의 입력/수정/삭제 시 성능 부하 적음(왜? 실제 데이터 페이지는 정렬과 무관하므로)
• 리프노드에서는 페이지 번호와 #오프셋을 가지고 있어 데이터 페이지의 특정 행에 대한 정보를 알 수 있음
• 리프 노드에서 데이터 페이지(실제 테이블)로 이동
• 논-클러스터 인덱스 생성 시 실제 데이터 페이지는 그대로 두고 별도의 인덱스 페이지에 구성한다.
  • 인덱스 내(별도의 페이지)에서 정렬하지만, 실제 데이터 페이지에서 물리적 순서는 변경되지 않는다.

※ 논 클러스터 인덱스와 클러스터 인덱스 혼합 사용

클러스터 인덱스와 논 클러스터 인덱스를 혼합해서 사용하는 경우도 많다. 이때는 논 클러스터 인덱스의 리프페이지에 클러스터 인덱스가 적용된 칼럼의 실제값(PK)이 저장된다. 같이 사용함으로써 복잡한 쿼리를 빠르게 처리하는 것이 가능하고, 범위 검색 및 정렬에 있어 이점을 가져올 수 있다.

 

인덱스 테이블 구조 속성 살펴보기

  SHOW INDEX FROM player;

Table	Non_unique	Key_name	Seq_in_index	Column_name	Index_type	Null
player	0	PRIMARY	1	id	BTREE
player	0	team_id_backnumber_idx	1	team_id	BTREE	YES
player	0	team_id_backnumber_idx	2	backnumber	BTREE	YES
player	1	player_name_idx	1	name	BTREE

• Non_unique: 0일 경우 중복값이 허용되지 않음, 1일 경우 중복값 허용
• Key_name : 해당 인덱스의 이름을 나타내는 속성 또는 열
• Seq_in_index : 인덱스 된 열(또는 열의 조합)의 순서를 나타내는 값. 복합 인덱스의 각 열에 대해 몇 번째 순서로 정의되었는지를 나타냄

4. 인덱스의 자료구조( Hash Table  VS B-Tree )

해시 테이블(Hash Table) [Hash에 대해 궁금하다면?]

해시 테이블 기반의 데이터베이스 인덱스는 (Key, Value) 형식으로 Key = 칼럼의 값, Value = 실제 데이터 주소를 담아 해시를 통해 인덱스를 구현하였다. 하지만 실제로 많은 DB에서는 해시테이블을 사용하지 않는다.

• 시간복잡도 O(1)의 성능
• 메모리 기반의 데이터베이스에서 많이 사용
• equality 비교만 가능, 범위에 대한 비교 불가능
• Rehashing에 대한 부담 : 데이터의 크기가 늘어나면 테이블의 크기도 늘려줘야 함.
• 정렬되어 있지 않음
• multicolumn index(2개 이상의 속성으로 이루어진 인덱스)의 경우 전체 속성에 대한 조회만 가능
  • B-Tree의 경우 (a, b) 인덱스 테이블에서 a만 검색이 가능했는데 해시로 구현하면 a만 검색이 불가능하다.

B-Tree

B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용된다. B-Tree에는 여러 가지 변형된 알고리즘이 있는데, 일반적으로 DBMS에서는 주로 B+Tree, B* Tree가 사용된다.

AVL 트리와의 비교

B-Tree는 AVL 트리와 비슷한 알고리즘을 사용하지만 B-Tree를 사용하는 이유가 있다. B-Tree는 하나의 노드에 여러 키 값을 가질 수 있는 반면 AVL트리는 노드 당 하나의 키값을 가질 수 있다. 

메모리 계층 구조

위의 메모리 계층 구조 그림을 잠깐 살펴보자.

하위로 갈수록 데이터의 처리속도가 느려진다. RAM에서 코드가 실행되고 결과를 가져오기 위해서는 Secondary storage에 있는 DB에 접근해야 한다. AVL 트리의 구조에서 Secondary storage 접근은 최악의 경우 트리의 레벨(높이)만큼 접근해야 한다. 그러나 B-Tree의 경우 더 넓은 범위 단위로 데이터를 저장하고 있기 때문에 AVL 트리보다 작은 트리의 레벨(높이)을 가지고 있다. 그러므로 Secondary storage의 접근 횟수를 줄일 수 있다. 또한 블록 단위로 데이터를 읽고 쓰는 메모리의 특성상 B-Tree가 성능면에서 더욱 유리하다.

 

B-Tree의 특징

B-Tree의 자료구조는 BST(Binary Search Tree)의 자료구조와 비슷하다. 부모노드를 기준으로 왼쪽에는 작은 값을 가진 자식의 노드, 오른쪽에는 자식보다 큰 값을 가진 자식의 노드들이 위치한다.(정확하게는 자식노드를 향하는 포인터를 가지고 있음) AVL 트리와 다른 점은 각 노드에 여러 개의 키를 저장하고 있다. 그러다 보니 한 번의 노드 탐색으로 여러 개의 키(데이터)를 검색할 수 있으며, 이는 검색 성능 향상으로 이어진다.

• B트리는 균형 트리의 구조를 가진다. 따라서 모든 리프노드가 동일한 레벨에 존재한다. 이러한 균형구조로 인해 검색, 삽입 및 삭제 작업의 평균 시간 복잡도가 O(log N)이 되어 효율적인 데이터 검색을 지원한다.
• 각 노드는 여러 개의 자식을 가질 수 있다.
• 각 노드에 저장된 키들은 항상 정렬된 상태를 유지한다.
• 연속적인 키 범위를 가지고 있기 때문에 범위 검색에 유리하다. 이것은 디스크 기반 시스템에서 I/O 비용을 줄이는 데 도움이 된다.
• 데이터 삽입과 삭제 시에 데이터 불균형이 발생할 경우 회전 및 재배치 연산을 통해 균형을 재조정한다.

---

참고한 자료

SQL queries on clustered and non-clustered Indexes - GeeksforGeeks

Difference between Clustered and Non-clustered index - GeeksforGeeks

데이터베이스 인덱스 (2) - 클러스터형 인덱스와 비클러스터형 인덱스

[데이터베이스] 클러스터 인덱스와 넌클러스터 인덱스/ 개념 총정리

클러스터드 인덱스와 넌 클러스터드 인덱스