[DB] 초보 개발자의 Index 탐구 일지 1편 : 자료구조, 동작원리,

프로젝트를 진행하며 처음으로 Index를 걸어 사용해보는 경험을 하고있습니다.

때문에 인덱스의 깊은 이해도를 위해 궁금했던 점에 대해 포스팅을 하려 합니다. 

 

목차는 다음과 같습니다.

• 인덱스의 자료구조
• 인덱스의 동작원리와 장단점
• Clustered Index vs Non-Clustered Index?
• 멀티컬럼 인덱스
• 어떤 컬럼에 적용하고, 어떤 연산에 쓰는게 좋을까?
• 언제나 인덱스를 적용하는 것이 더 빠를까?
• 왜 클러스터가 읽기에서 더 빠른 성능을 보이는가?

 

---

인덱스의 자료구조

 

# HashTable

 

• key - value 를 한 쌍으로 저장하는 자료구조
• Hash Colision이라는 변수가 존재하지만, O(1) 의 시간복잡도로 빠르게 데이터를 조회할 수 있음
• =(eq)연산에 최적화되어있기 때문에, <, > 등 범위연산이 많은 DB에서 잘 사용되지 않음
• 해시테이블의 특성 상 정렬도 되어있지 않기 때문에 DB 데이터 탐색에 효율적이지 않음

 

# B-Tree

 

• 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리
• 정렬된 상태를 보장할 수 있으며 Root노드로부터 Leaf노드까지의 평균 시간복잡도 O(logN)
• 한 노드당 2개 이상의 노드를 가질 수 있어 이진트리보다 효율이 높으며, 데이터와 포인터를 모두 갖고있음
• 데이터 갱신(insert, update, delete)가 반복되다보면 균형이 깨질 위험이 있으며, 성능이 악화될 우려 있음
• 탐색 시 중위순회를 하기 떄문에 상당히 많은 노드를 탐색해야 하는 단점 존재

 

# B+Tree

• B-Tree가 발전한 형태, leaf 노드에만 데이터를 보관하고 중간의 branch노드에는 포인터만 보관하기 떄문에 메모리를 덜 차지해 B-Tree보다 더 많은 인덱스의 키를 보관할 수 있음
• 더 많은 키를 보관하는 만큼 Root노드부터 Leaf노드까지의 높이가 낮아져 더 빠른 속도로 탐색 가능
• Leaf노드들끼리 LinkedList로 되어있어 B-Tree처럼 중위순회를 할 필요 없이 말단노드끼리의 탐색을 한번만 하면 됨
• 단, 특정 인덱스 키에 접근하기 위해 무조건 leaf 노드까지 도달해야 한다는 단점이 있음

---

동작원리와 장단점

• Insert : 새로운 데이터에 대한 인덱스 추가
• Delete : 삭제하는 데이터의 인덱스 사용하지 않는다는 표시
• Update : 기존 인덱스 사용하지 않음 처리, 갱신되는 데이터의 인덱스 추가(Delete + Insert)

 

장점

• 테이블 검색 속도와 성능 향상
• 인덱스에 의해 정렬된 형태의 데이터를 얻을 수 있음. 기존 Full Table Scan에서 where문의 조건을 일일히 대입하기보다는, 정렬된 데이터에서 공간지역성의 특징을 통해 높은 향상을 기대할 수 있음

단점

• 인덱스는 Read의 성능 향상을 위해 Insert, Delete, Update의 성능을 포기하는 것과 같음
• 인덱스 관리를 위한 별도의 작업과 저장공간 필요
• 잘못 사용하는 경우 오히려 성능 저하

 

왜 Read의 성능은 좋아지는 대신 Insert, Delete, Update의 성능은 낮아질까??

 

키가 삽입될 때는 분할과정이 일어나고, 키를 삭제할때는 병합과정이 일어나기 때문

 

또한 Delete, Update시 기존의 인덱스를 삭제하는 것이 아닌 "사용하지 않음" 처리를 함으로써 데이터가 점점 커져 부하를 줄 수 있고, 이를 담기 위한 추가적인 저장공간이 필요하다.

 

때문에 Write연산이 비교적 적은 테이블에 사용하는 것이 합리적이다.

 

인덱스를 사용하기 좋은 예시와 사용했을 때 오히려 성능이 나빠지는 경우 등은 다음 포스팅에서 다루겠다.

 

---

Clustered Index vs Non-Clustered Index

 

Clustered Index

 

• 테이블 당 한개만 존재 가능한 인덱스
• Primary Key 속성의 컬럼에 자동적으로 생성됨
• 지정된 컬럼에 대해 물리적으로 재배열(인덱스 생성 시 테이블 전체를 재배열)
• 삽입 순서와 관계없이 Index 컬럼을 기준으로 정렬되어 삽입됨( = 삽입, 삭제, 수정 시 테이블이 정렬됨)
• 인덱스 페이지는 <키 - 데이터페이지 번호>로 구성되며, 이를 사용해 데이터를 검색

 

• 리프페이지가 데이터 그 자체이기 떄문에 검색 속도가 월등히 빠름
• Index 자체에 데이터가 포함되어있는 구조
• 물리적 데이터를 직접 재배열하기 때문에 추가 공간이 필요하지 않음

 

Non-Clustered Index

 

 

• 물리적으로 데이터를 재배열하지 않고, 테이블의 데이터를 건들지 않으며 지정된 컬럼에 대해 정렬된 인덱스를 생성하는 방식
• 검색속도는 Clustered Index보다 떨어지나, Insert/Delete/Update에 한해서는 더 빠름
• 테이블 당 여러개 존재 가능하며, 남용 시 성능 저하
• 데이터의 행에 독립적이며 <인덱스 키 - 데이터를 가리키는 포인터>로 이루어져 있음

 

• 실제 데이터인 데이터페이지는 정렬되어있지 않으며, 인덱스만 정렬되어있는 것을 확인할 수 있음
• 데이터가 자주 업데이트 되거나 조건문, 필터링이 자주 사용되는 테이블에 적합
• 저장되는 별도의 공간(약 테이블의 10%) 필요

---

출처

https://rebro.kr/167

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

 

https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/

DB Index 입문

https://jojoldu.tistory.com/243

[mysql] 인덱스 정리 및 팁

https://velog.io/@gillog/SQL-Index%EC%9D%B8%EB%8D%B1%EC%8A%A4

[SQL] Index(인덱스)

https://kyungyeon.dev/posts/66

DB Index 동작원리를 알아보자

https://gwang920.github.io/database/clusterednonclustered/