DB INDEX

HunkiKim·2022년 9월 20일

INDEX

기본적인 정의는 정의는 목차라는 뜻이다. 즉 무언가를 찾을 때 편하게 찾기 위해 인덱스를 사용해 찾는 것처럼 찾고 싶은 내용에 대해 이를 주요 내용이나 페이지를 함께 써놓은 것들을 말한다. DB에서도 마찬가지로 어떤 데이터를 찾을 때 사용하는 목차와 비슷한 느낌으로 사용된다.

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 쉽게 생각하면 목차(index)라고 생각하면 된다. 책에서 원하는 내용을 찾을 때 목차를 보고 찾으면 더 빠르게 찾는 것처럼 위치를 추가적인 공간을 통해 쉽게 찾을 수 있게하는 자료구조이다.

장점

테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
전반적인 시스템의 부하를 줄일 수 있다.

단점

인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
인덱스를 관리하기 위해 추가 작업이 필욯다.
인덱스를 잘못 사용할 경우 오히려 성능이 저하돼 역효과가 발생할 수 있다.

간단하게 읽는 것은 빨라지지만 갱신(삽입, 삭제, 수정 update)에 대해서는 느려지는 Trade-off 관계에 있다.

삽입이나 수정시에는 해당 인덱스를 다시 정렬해야하고, update와 달리 delete는 기존 인덱스를 삭제하지 않고 '사용하지 않음'처리를 해주기 때문에 update와 delete가 빈번하게 발생하면 실제 데이터에 비해 인덱스가 10배이상 많은 상황도 가능하다.

문법에 따른 동작

SELECT : 특별한 방식으로 정렬된 목차를 통해 빠르게 데이터를 찾는다.
INSERT : 삽입을 할 때 페이지가 꽉 차게 되는 경우 페이지가 분리된다. 이렇게 될 경우 다시 새로운 고정된 크기의 페이지를 새로 만들고 키도 옮겨야 하고 Redo에 모든 수행 과정이 기록되어야 한다. 즉 실제 자원적으로도 그렇고 수행함에 있어서의 자원도 소모가 많이 된다.
DELETE : 인덱스의 데이터를 Soft Delete를 한다. 리프 노드의 값을 삭제하지 않고 행이 지워졌다는 표시만 한다. 따라서 데이터를 읽을 때 이 표시가 읽기 때문에 데이터를 읽지 않는다. 이는 클러스터 인덱스나 논 클러스터 인덱스 리프레벨에서 모두 일어나게 된다.
UPDATE : 업데이트는 실제로 많은 작업이 일어나지만 짧게 말하면 기존의 데이터를 DELETE 한 뒤 수정할 값을 다시 INSERT 한다.

사용하면 좋은 곳

규모가 작지 않은 테이블
insert, update, delete가 자주 발생하지 않는 컬럼
join이나 where, oreder by에 자주 사용되는 컬럼
데이터의 중복도(카디널리티)가 낮은 컬럼

인덱스의 자료구조

해시 테이블(Hash Table)

인덱스의 자료구조에는 해시 테이블과 B+-트리가 있는데 해시 테이블은 (Key,Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. Key값을 이용해 고유한 index를 생성하여 index에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB 인덱스는 (데이터=컬럽의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 (=) 등호 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(<,>)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

B+Tree

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선 시킨 자료구조이다.

리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
리프노드들은 LinkedList로 연결되어 있다.
데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화 하였따. (몰론 Best Case에 대해 리프노드까지 가지않아도 탐색 가능한 BTree와 달리 무조건 리프노드까지 가야하는 단점이 있다.)

그래서 B+Tree는 O(log2nlog2n)의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 접합한 자료구조가 되었다.

B+Tree는 즉 리프노드가 실제 데이터이고 이를 링크드 리스트로 연결해 찾은 값을 순서대로 보기 쉽지만 무조건 리프노드까지 가야함.

클러스터형 인덱스(Clustered Index) vs 비클러스터형 인덱스(Non-Clustered Index)

클러스터형
- 무리, 군집 또는 무리를 이루다라는 의미이다. 즉 실제 데이터와 무리를 이루는 경우를 말한다.
- 클러스터형 인덱스는 해당 키 값을 기반으로 테이블이나 뷰의 데이터 행을 정렬하고 저장한다. 인덱스 정의에 여러 열이 포함된다. 데이터 행 자체는 한 가지 순서로만 저장될 수 있고 테이블당 클러스터형 인덱스는 하나만 있을 수 있다.
- 테이블의 데이터 행이 정렬된 순서로 저장될 떄만 테이블에 클러스터형 인덱스가 포함된다. 클러스터형 인덱스가 포함된 테이블을 클러스터형 테이블이라고 한다. 테이블에 클러스터형 인덱스가 없으면 해당 데이터 행은 힙이라는 정렬되지 않은 구조로 저장된다.
- Primary Key를 적용하면 클러스터링 인덱스가 자동으로 생성된다. 혹은 Unique + Not null도 가능하지만 두 개 다 걸려있는 경우 Primary Key를 우선으로 하여 생성된다.
비클러스터형 인덱스
- 클러스터형과 반대로 실제 데이터와 무리를 이루지 않는다.
- 비클러스터형 인덱스의 구조는 데이터 행으로부터 독립적이다. 비클러스터형 인덱스에는 비클러스터형 인덱스 키 값이 있으며 각 키 값 항목에는 해당 키 값이 포함된 데이터 행에 대한 포인터가 있다.
- 비클러스터형 인덱스의 인덱스 행에서 데이터 행으로의 포인터를 행 로케이터라고 한다. 행 로케이터의 구조는 데이터 페이지가 힙에 저장되는지 아니면 클러스터형 테이블에 저장되는지에 따라 다르다. 힙의 경우 행 로케이터는 행에 대한 포인터이다. 클러스터형 테이블의 경우 행 로케이터는 클러스터형 인덱스 키이다.
- unique 제약 조건을 걸게되면 non-clustering 자동으로 생성된다.

클러스터형 인덱스는 실제로 트리의 leaf node에 데이터가 정렬되어 있다. 따라서 하나의 테이블에는 하나의 클러스터형 인덱스를 가질 수 있다. (primary key 설정시 자동으로 클러스터형 인덱스 생성)

비클러스터형 인덱스는 실제 정렬된 데이터를 가지는 것이 아니라 leaf node에 해당 데이터의 링크를 가지고 있는 구조이다.

클러스터형 인덱스는 행 데이터를열로 정렬하고, 루트페이지를 만든다. 그리고 클러스터형 인덱스는 루트페이지와 리프 페이지로 구성되며, 리프 페이지는 데이터 그 자체이다. 즉 인덱스가 정렬되며 각 인덱스의 행이 고유하게 페이지로 구성된다. PRIMARY KEY 조건을 사용하면 고유 인덱스가 자동으로 생성되는데 기본적으로 클러스터형 인덱스가 생성된다. 따로 설정을 해야 비클러스터형이된다.

비클러스터형 인덱스는 데이터 페이지를 건들지 않고, 별도의 장소에 인덱스 페이지를 생선한다. 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열을 정렬한 후 위치 포인터를 생성한다. RID 구조 : 파일식별자 + 페이지번호 + 페이지내의 행 번호로 구성된다. 즉 루트페이지에 인덱스로 구성한 열을 정렬하고 데이터 위치 포인터를 생선한다. 그리고 데이터 위치 포인터로 리프 노드를 가리키면 그 안에 페이지 번호 + #오프셋이 기록되어 바로 데이터 위치를 가리킨다. 그리고 이 데이터 위치 포인터는 데이터가 위치한 고유한 값이 된다. 즉 루트노드 -> 인덱스 페이지 -> 데이터 페이지로 인덱스 페이지를 거치게 된다.