데이터베이스의 인덱스
DB의 인덱스 👉 책의 찾아보기?!
책 뒷편에 존재하는 찾아보기 페이지에는 책의 핵심 키워드가 사전순으로 정렬되어 있다!
이처럼 데이터베이스의 인덱스는 책의 찾아보기 페이지와 많이 닮아있다.
둘 다 추가적인 저장공간(책 페이지)에 미리 정렬된 정보를 저장하여, 원하는 데이터(책 내용)를 찾기 위해 사용된다.
즉 데이터베이스의 인덱스란, 추가적인 저장 공간을 사용해서 테이블 검색 속도를 향상시키기 위한 자료구조다!!!
데이터베이스 인덱스에는 데이터의 키와 해당 데이터의 물리적 위치가 나타나 있다.
👉 ex) ‘키가 10번인 데이터는 테이블 35번 행에 저장되어 있다’
인덱스는 일반적으로 SELECT 쿼리의 WHERE 절에 사용될 컬럼에 대한 조회 성능을 개선할 때 사용된다!
인덱스를 사용하는 이유
조건 검색 Where 절의 효율성
테이블을 만들고 안에 데이터가 쌓이게 되면 테이블의 레코드는 내부적으로 순서가 없이 뒤죽박죽으로 저장된다.
이렇게 되면 Where절의 특정 조건에 맞는 데이터들을 찾아낼 때도 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 비교해야 한다. (이것을 풀 테이블 스캔, Full Table Scan 이라고 함)
하지만 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건 (Where)에 맞는 데이터들을 빠르게 찾아낼 수 있게 된다!!
정렬 Order By 절의 효율성
인덱스를 사용하면 Order By에 의한 Sort 과정을 피할 수 있게 된다!!
사실 Order By는 굉장히 부하가 많이 걸리는 작업으로 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생된다고 한다…
하지만 인덱스를 사용하면 이러한 전반적인 자원의 소모를 하지 않아도 된다!!
MIN, MAX의 효율적인 처리 가능
이것 또한 데이터가 정렬되어 있기에 얻을 수 있는 장점!!
MIN, MAX 값을 레코드의 시작 값과 끝 값을 가져오기만 하면 되기 때문!
Full Table Scan으로 테이블을 다 뒤져서 작업하는 것보다 훨씬 효율적!
💡 이런 식으로 검색하는 속도가 매우 빨라지다보니 결과적으로 컴퓨터의 부담이 줄어들어서 전체 시스템의 성능이 향상된다!!!
인덱스의 단점
인덱스는 DML에 취약
INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다.
그리고 인덱스 테이블, 원본 테이블 두 군데의 데이터 수정 작업을 해줘야 한다..
👉 그렇기 때문에 DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋다!!
무조건 인덱스 스캔이 좋은 것은 아니다
인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 낫다!!
직관적인 예시를 들자면,
1개의 데이터가 있는 테이블과 100만 개의 데이터가 들어 있는 테이블이 있다고 하자. 100만 개의 데이터가 들어있는 테이블이라면 풀 스캔보다는 인덱스 스캔이 유리하겠지만, 1개의 데이터가 들어있는 테이블은 굳이 인덱스 스캔 없이 풀 스캔이 빠를 것이다.
인덱스를 위한 추가 저장 공간..
인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다!
👉 속도 향상에 비해 단점들의 cost를 비교해서 인덱스를 만들지 말지를 정해야 한다!
인덱스 자료구조
1. 해시 테이블(Hash Table)
해시 테이블은 Key를 사용하여 원하는 자료에 빠르게 접근하는 대표적인 자료구조로 Key-Value 쌍으로 데이터를 저장한다!
데이터의 Key를 알고 있으면 데이터에 O(1)의 시간 복잡도로 접근할 수 있기 때문에 데이터베이스에 적합한 자료구조 보여진다.
하지만 데이터베이스에서는 부등호 연산이 자주 발생하기 때문에 해시 테이블은 적합하지 않은 자료구조이다..
해시 테이블의 데이터는 정렬되어 있지 않으므로, “Key가 400보다 작은 데이터”를 찾기 위해서는 모든 데이터에 접근해야 한다.
부등호 연산을 제외하고도 NOT 연산, ‘~로 시작하는 데이터 찾기’ 등에서 모두 불리한 모습을 보인다..!
2. B-Tree
우선 Tree 자료 구조에 대하여,
일반적으로 Tree는 평균적으로 탐색에 대해 O(logN)이라는 시간 복잡도를 가지지만 한 쪽으로 편향되는 최악의 경우에는 O(N)이 된다.
이러한 경우를 방지하기 위해 밸런스 트리(Balanced Tree)를 이용한다!
밸런스 트리(Balanced Tree)란?! 🤔
트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다.
B-Tree가 선택된 이유 🤔
B-Tree는 위처럼 노드 하나에 여러 데이터가 저장될 수 있다.
각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. 👉 n + 1개의 자식 노드
각 노드에는 여러 개의 key를 가지고 있고 각 key에 대응하는 Data도 함께 갖고 있다!
💡 키(key)와 포인터(pointer)
데이터베이스에서는 B-Tree의 노드를 페이지 또는 블럭이라고 부르며, 노드 내의 데이터를 키(Key)라고 부른다. 또한 노드 내부의 키들은 항상 오름차순으로 정렬된 상태를 유지한다.
각 노드의 키들은 좌우로 다른 노드를 가리키는 포인터를 가지고 있다. 좌측 포인터는 키보다 작은 데이터를 가진 노드를 , 우측 포인터는 키보다 큰 데이터를 가진 노드를 가리킨다.
💡 데이터 포인터(data pointer)
노드의 각 키는 실제 데이터의 물리적 위치를 가리키고 있는 데이터 포인터(data pointer)를 가지고 있다. 키를 기준으로 데이터를 탐색한 뒤, 일치하는 키를 발견한 경우 데이터 포인터가 가리키는 곳으로 이동해 실제 데이터를 찾을 수 있다.
데이터베이스에서는 특정 컬럼으로 인덱스를 생성할 수 있는데, 이때 컬럼의 값이 키가 되고, 테이블의 행(데이터의 물리적 위치)는 데이터 포인터가 된다.
❓ B-Tree의 key 검색
원하는 값을 K라고 가정하면,
1. root node부터 탐색을 시작한다.
2. node의 key를 순회하여 K가 존재하면 탐색을 종료한다.
3. K가 존재하지 않는다면, 어떤 이웃한 두 key 사이에 K가 들어가는 경우 사이의 포인터를 통해 자식 node로 내려간다.
4. leat node까지 2~3을 반복한다.
👉 https://rebro.kr/169
3. B+Tree
B+Tree는 B-Tree를 개선시킨 자료구조이다. 실제로 MySQL(InnoDB) 등 많은 DBMS에서는 B-Tree 대신 B+Tree를 사용한다.
기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 (부등호 연산처리할 때 라던가..) 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다!!
B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다. 그리고 leaf node끼리는 Linked list로 연결되어있다.
또, B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.
B+Tree의 장점
- B+Tree는 leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다!!
- Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.
B+Tree의 단점
B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 한다…
클러스터형 인덱스 (Clustered Index)
클러스터형 인덱스 👉 영어사전?!
클러스터형 인덱스는 테이블 전체가 정렬된 인덱스가 되는 방식의 인덱스 종류다. 데이터와 함께 전체 테이블이 물리적으로 정렬된다!
실제 데이터와 무리(cluster)를 지어 인덱싱 되므로 클러스터형 인덱스라고 부른다!
클러스터형 인덱스는 테이블당 하나만 생성할 수 있다. 그렇기 때문에 어떤 컬럼을 선택해 클러스터형 인덱스를 만들지에 따라 성능이 좌우될 수 있다!
특정 컬럼을 PK로 지정하면 자동으로 클러스터형 인덱스를 생성한다.
클러스터형 인덱스는 위 그림처럼 B+Tree의 형태로 구성되어 있다. 앞으로 여기서 B+Tree의 노드를 데이터베이스에서는 페이지라고 부른다. 각 페이지는 고유의 페이지 번호를 가지고 있다. 위 그림은 rank 컬럼을 PK로 설정해 클러스터형 인덱스를 생성한 모습이다.
루트 페이지를 보면 Key로는 PK를 가지고 있고, 포인터로는 다른 페이지의 페이지 번호를 가지고 있다. 또, 리프 페이지는 Key로 PK를 가지고 있고, 데이터를 직접 가지고 있는 것을 확인할 수 있다.
비클러스터형 인덱스 **(Non-Clustered Index)**
비클러스터형 인덱스 (보조 인덱스) 👉 일반 책의 뒷 장에 존재하는 찾아보기?!
클러스터형 인덱스와는 다르게 물리적으로 테이블을 정렬하진 않고, 별도의 인덱스 페이지를 생성하고 관리한다!!
👉 즉 실제 데이터를 함께 가지고 있지 않다!!
또한 비클러스터형 인덱스는 테이블당 여러개 생성 가능하며 Unique 키를 지정하면 자동으로 보조 인덱스를 생성한다!
CREATE [UNIQUE] INDEX 인덱스_이름 ON 테이블_이름 (열_이름) [ASC | DESC]
DROP INDEX 인덱스_이름 ON 테이블_이름
비클러스터형 인덱스는 위의 그림처럼 인덱스 페이지와 데이터 페이지가 구분되어있다.
루트 페이지는 클러스터형 인덱스와 비슷하게 인덱스에 대한 컬럼과 페이지 번호를 가지고 있다.
리프 페이지는 조금 다르다. 인덱스 컬럼을 가지고 있는 것은 비슷하지만, 데이터를 직접 가지고 있지 않으며 데이터 페이지 번호 + #오프셋 을 가지고 있어 데이터 페이지의 특정 행을 가리킨다.
👉 즉, 데이터에 접근하기 위해서는 인덱스 페이지에서 데이터 페이지로 이동하는 하나의 과정이 추가된다.
인덱스 페이지는 정렬되어 있지만, 실제 데이터 페이지는 정렬되지 않으므로 클러스터형 인덱스에 비해 삽입, 수정, 삭제 작업이 비교적 빠르다. 데이터 페이지에는 정렬 순서 상관없이 빈 곳에 데이터를 삽입하면 되기 때문이다.
💡 **클러스터형 인덱스와 비클러스터형 인덱스의 혼합**
현실적으로는 하나에 테이블에 클러스터형 인덱스와 비클러스터형 인덱스가 혼합되어 있는 경우가 많다고 한다.
PK는 기본적으로 존재하고, 추가로 조회가 자주 발생하는 컬럼에 대해 인덱스를 추가하기 때문이다.
이러한 경우에는 비클러스터형 인덱스를 먼저 거치고, 이어 클러스터형 인덱스를 거쳐 데이터를 찾는다. 이때, 비클러스터형 인덱스는데이터 페이지 번호 + #오프셋대신 클러스터형 인덱스에 대한 컬럼 값을 갖는다.
인덱스 대상 컬럼 선택 기준, 카디널리티
인덱스 대상 컬럼은 카디널리티(cardinality)가 높은 컬럼을 우선적으로 선택해야 유리하다.
카디널리티 🤔
데이터 집합에서 유일한 데이터의 개수
예를 들어 대한민국 국민 테이블을 인덱싱할때 카디널리티가 낮은 성별 컬럼 대신 카디널리티가 높은 주민번호 컬럼을 인덱싱 하는 것이 바람직한다.
📚 참고 자료
데이터베이스 인덱스 (1) - 인덱스와 인덱싱 알고리즘 (hash table, b-tree, b+tree)
[DB] 데이터베이스 인덱스(Index) 란 무엇인가?
데이터베이스 인덱스 (2) - 클러스터형 인덱스와 비클러스터형 인덱스
