1️⃣ 개념
DB에서 테이블에 대한 검색 속도를 향상시켜주는 자료구조
- 테이블의 특정 컬럼에 대한 인덱스를 생성하면, 해당 컬럼을 기준으로 데이터를 정렬한 후 별도의 메모리 공간에 물리적 주소(DB내에 저장된 데이터의 주소)와 함께 저장됨
- 컬럼값과 물리적 주소를 (key, value)의 한 쌍으로 저장함
- 보통 인덱스는 테이블 크기의 10%정도의 저장공간을 차지
장점
- 테이블을 검색하는 속도와 성능이 향상되어, 시스템의 전반적인 부하를 줄일 수 있음
- 인덱스에 의해 데이터들이 정렬된 형태를 갖기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있음
- ORDER BY, MIN/MAX 같은 경우도 이미 정렬되어 있으므로 빠르게 수행 할 수 있음
단점
- 인덱스를 관리하기 위한 추가 작업 및 저장공간이 필요함
- 인덱스는 항상 정렬된 상태로 유지되기 때문에, 인덱스가 적용된 컬럼에 삽입/삭제/수정 작업을 수행하면 아래의 추가 작업이 필요함 -> 즉, 수정이 잦은 경우 성능이 낮아짐
- INSERT: 새로운 데이터에 대한 인덱스 추가
- DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행
- UPDATE: 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가
- 잘못 사용하는 경우 오히려 검색 성능이 저하됨
- 데이터를 제거할 경우, 인덱스도 제거하는 것이 아니라 해당 인덱스는 ’사용하지 않음’으로 처리하고 남겨두기 때문에 수정 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 많아질 수 있음
❓ 장점보다 단점이 많아보이는데 인덱스를 사용하는 이유는?
일반적인 OLTP(온라인 트랜잭션 처리) 시스템에서는 데이터 조회 업무가 90% 이상이기 때문
인덱스를 사용하면 좋은경우
- 규모가 큰 테이블
- 삽입, 수정, 삭제 작업이 자주 발생하지 않는 칼럼
- WHERE, ORDER BY, JOIN 등이 자주 사용되는 칼럼
- 데이터의 중복도가 낮은 칼럼
2️⃣ 인덱스 구현 자료구조
해시 테이블
(Key, Value)를 한쌍으로 저장하여, Key값을 이용해 대응되는 Value값을 구함
해시충돌 가능성은 있지만, 평균적으로 O(1)에 데이터 탐색이 가능함
But, 실제 인덱스에서는 잘 사용되지 않음
-> 등호 연산에 최적화 되어있기 때문, DB에서는 부등호 연산이 자주 사용되는데, 해시 테이블 내 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내에 찾을 수 없음
B 트리
트리 자료구조의 일종으로, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식노드의 숫자가 2보다 큰 트리 구조
이진 검색 트리와 달리 균형 이진 트리임
✨ 특징
- 노드에는 2개 이상의 데이터(Key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장됨
- 위 그림에서 한 노드에 (7,15)가 정렬된 상태로 저장되어 있음
- 특정 노드의 왼쪽 서브 트리는 특정 노드의 Key보다 작은 값들로, 오른쪽 서브트리는 큰 값들로 구성됨
- 노드 내에서 key가 a1, a2, a3... 등으로 존재한다면, a1 왼쪽 서브 트리는 a1보다 작아야 하고, a1과 a2 사이의 서브 트리는 a1보다는 크면서 a2보다는 작아야 함
- (7,15) 사이의 서브트리는 7보다는 크지만 15보다는 작은 값들이 위치함
- 리프 노드를 제외한 내부 노드는 M/2 ~ M개의 자식을 가질 수 있음. "최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 함"
- M=3 -> 3차 B트리, 1~3개의 자식 노드 가능
- 특정 노드의 데이터(Key)가 K개라면, 자식 노드의 개수는 K+1개여야 함
- 위 그림에서 루트 노드의 데이터는 2개이므로, 자식 노드의 개수는 3개임
- 노드 내에 데이터는 floor(M/2)-1개부터 최대 M-1까지 포함될 수 있음
- 3차 B트리는 각 노드에 floor(3/2)-1=0개 부터 최대 2개의 데이터를 가질 수 있음
- 모든 리프 노드들은 같은 레벨에 존재해야 함
✨ 장점
- 하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담을 수 있게 됨
- 균형 이진 트리이기 때문에, 아무리 최악의 경우라도 O(logN)의 검색 성능을 보여줌
✨ 단점
- 균형 이진 트리 구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성되어야 함
- 순차탐색 시 중위순회 방식으로 진행되어 비효율적임
B+ 트리
B-tree의 순차탐색을 효율적으로 하기위해 B+tree가 등장함
특정 값을 찾아야 하는 상황이 된다면 리프 노드에 모든 자료들이 존재하고, 그 자료들이 연결리스트로 연결되어 있으므로 탐색에 있어서 매우 유리함!
오늘날 데이터베이스에서 가장 중요한 것은 검색속도이기 때문에 대부분의 데이터베이스 시스템은 B+Tree구조를 채택하고 있음
✨ 특징
- 리프 노드가 아닌 자료는 인덱스 노드라고 부르고, 리프 노드는 데이터 노드라고 부름
- 인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재
- 데이터 노드의 Value값에 데이터가 존재
- 키 값은 중복될 수 있고(인덱스 노드와 데이터 노드에서 동시에 등장 가능함), 데이터 검색을 위해서는 반드시 리프 노드까지 내려가야 함
- 데이터 노드의 자료는 정렬되어 있으며, 데이터 노드의 자료는 중복되지 않음
- 모든 리프 노드는 같은 레벨에 있으며, 연결리스트로 연결되어 있음
✨ 장점
- 리프 노드를 제외하고 데이터를 저장하지 않아 메모리를 더 확보할 수 있음
- 하나의 노드에 더 많은 포인터를 가질 수 있으므로 트리의 높이가 낮아져 검색속도를 높일 수 있음
- 모든 노드를 확인해야 하는 B-tree와 달리, Full scan 하는 경우 리프노드에만 데이터가 저장되어 있고 연결리스트로 연결되어있으므로 선형시간이 소모됨
✨ 단점
- B-tree는 최상의 경우 특정 데이터를 바로 루트 노드에서 찾을 수 있지만, B+ tree는 반드시 리프 노드까지 가야함
3️⃣ 인덱스의 종류
클러스터형 인덱스 (Clusted Index)
- 클러스터형 인덱스를 구성하기 위해서, 행 데이터를 해당 열로 정렬한 후에 루트 페이지를 만들게 됨
- 클러스터형 인덱스는 트리로 저장되며, 루트 페이지와 리프 페이지로 구성됨
또한 루트 페이지는 리프 페이지의 주소로 구성되며, 리프 페이지는 실제 데이터로 구성됨 - 테이블당 단 하나의 클러스터형 인덱스만 존재할 수 있음
- 클러스터형 인덱스 순서로 데이터들이 하드디스크에 저장됨
만약 클러스터형 인덱스를 따로 지정하지 않으면, 기본 키가 클러스터형 인덱스가 됨
- 데이터 입력, 수정, 삭제 시 항상 정렬된 상태를 유지함 -> 검색 속도가 넌클러스터형 인덱스보다 빠름
- 대신 넌클러스터형 인덱스보다 데이터 입력/수정/삭제 속도는 느림
- 따라서, 읽기 작업이 많고 데이터가 자주 업데이트되지 않는 경우 사용함
넌클러스터형 인덱스 (Non-Clustered Index)
- 레코드 원본은 정렬되지 않고, 인덱스 페이지만 정렬됨
즉, 넌클러스터형 인덱스는 데이터 페이지를 건드리지 않고 별도의 장소에 인덱스 페이지를 생성함 - 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열을 정렬한 후 위치 포인터(RID)를 생성함. 즉, 넌클러스터형 인덱스의 인덱스 페이지(리프 페이지)는 키값과 데이터가 위치하는 포인터(RID)로 구성됨
- 테이블당 여러 개(약 240개)의 넌클러스터형 인덱스를 만들 수 있음
- 클러스터형보다 검색 속도는 더 느리지만 데이터의 입력, 수정, 삭제는 더 빠름
- 인덱스를 생성할 때 데이터 페이지는 그냥 둔 상태에서 별도의 인덱스 페이지를 따로 만들기 때문에 용량을 더 차지함
- 따라서 데이터가 자주 업데이트 되는 경우나, Where절이나 Join 절과 같이 조건문을 활용하여 테이블을 필터링 하고자 할 경우 사용함
참고자료
인덱스 관련 질문 모음 -> https://land-turtler.tistory.com/120
https://code-lab1.tistory.com/217
[책] 면접을 위한 CS전공지식 노트
https://rebro.kr/167
https://mangkyu.tistory.com/96
https://unabated.tistory.com/entry/OLTP-OLAP
https://siahn95.tistory.com/77
https://azderica.github.io/00-db-index/
https://mongyang.tistory.com/75
https://velog.io/@sweet_sumin/클러스터드-인덱스-Clustered-Index-넌-클러스터드-인덱스-Non-Clustered-Index
