인덱스

Karter·2022년 5월 20일

데이터베이스

목록 보기

6/8

Index?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조. + 없는 값을 빠르게 찾을 수도 있다.
특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장
인덱스 생성 컬럼을 Where 조건으로 거는 등의 작업을 하면 옵티마이저에서 판단하여 생성된 인덱스를 탈 수 있다.
만약 인덱스를 타게 되면 아래의 그림과 같이 인덱스를 타게 되고 먼저 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식으로 동작을 하여 검색 속도의 향상을 가져올 수 있다.
인덱스는 책에 있는 목차.

Index 사용 이유

조건 검색 Where 절의 효율성

테이블을 만들고 안에 데이터가 쌓이게 되면 테이블의 레코드는 내부적으로 순서가 없이 뒤죽박죽으로 저장된다.
이렇게 되면 Where절에 특정 조건에 맞는 데이터들을 찾아낼때도 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 비교해야 한다 (Full Scan).
하지만 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건 (Where)에 맞는 데이터들을 빠르게 찾아낼 수 있다.

정렬 Order by 절의 효율성

인덱스(Index)를 사용하면 Order by에 의한 Sort과정을 피할수가 있다.
Order by는 굉장히 부하가 많이 걸리는 작업. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생.
하지만 인덱스를 사용하면 이러한 전반적인 자원의 소모를 하지 않아도 된다. 이미 정렬이 되어 있기 때문에 가져오기만 하면 된다.

MIN, MAX의 효율적인 처리가 가능

MIN값과 MAX값을 레코드의 시작값과 끝 값 한건씩만 가져오면 되기에 FULL TABE SCAN으로 테이블을 다 뒤져서 작업하는 것보다 훨씬 효율적으로 찾을 수 있다.

Index 관리

index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색.
그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생.

INSERT: 새로운 데이터에 대한 인덱스를 추가함
DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

Index 단점

인덱스의 가장 큰 문제점은 정렬된 상태를 계속 유지 시켜줘야 한다. 그렇기에 레코드 내에 데이터값이 바뀌는 부분이라면 악영향. INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 INDEX 테이블 내에 있는 값들을 다시 정렬을 해야한다. 그리고 INDEX 테이블, 원본 테이블 이렇게 두 군데에 데이터 수정 작업해줘야 한다는 단점.
검색시에도 인덱스가 무조건 좋은 것이 아니다. 인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 낫다. 그리고 인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요합니다. 무턱대고 INDEX를 만들어서는 결코 안된다.

인덱스 생성 전략

생성된 인덱스를 가장 효율적으로 사용하려면 데이터의 분포도는 최대한으로 그리고 조건절에 호출 빈도는 자주 사용되는 컬럼을 인덱스로 생성하는 것이 좋다.
인덱스는 특정 컬럼을 기준으로 생성하고 기준이 된 컬럼으로 정렬된 Index 테이블이 생성.
가장 최선은 PK로 인덱스를 거는 것.

조건절에 자주 등장하는 컬럼
항상 = 으로 비교되는 컬럼
중복되는 데이터가 최소한인 컬럼 (분포도가 좋은) 컬럼
ORDER BY 절에서 자주 사용되는 컬럼
조인 조건으로 자주 사용되는 컬럼

인덱스 자료구조

해시 테이블

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조.
해시 인덱스는 동등 비교 검색에는 최적화돼 있지만 범위를 검색한다거나 정렬된 결과를 가져오는 목적으로는 사용할 수 없다.
일반적인 DBMS에서 해시 인덱스는 메모리 기반의 테이블에 주로 구현돼 있으며 디스크 기반의 대용량 테이블용으로는 거의 사용되지 않는다는 특징.
값을 변형해서 인덱싱하므로 특정 문자로 시작하는 값으로 검색하는 전방 일치와 같이 값의 일부만으로 검색할 때는 사용 불가하다.

B-Tree

Key의 왼쪽 자식은 항상 Key보다 작은 값을, 오른쪽 자식은 큰 값
Tree 기반의 DB Index는 특정 컬럼의 값(Key)에 해당하는 노드에 데이터의 위치(Value)를 저장.
B-Tree의 Key, Value 값들은 항상 Key를 기준으로 오름차순 정렬.
이로 인해 부등호 연산(>, <)에 대해 해시 테이블보다 효율적인 데이터 탐색이 가능.
B-Tree는 균형 트리(Balanced Tree)로서, 최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일하기 때문에 평균 시간 복잡도는 O(logN).
Index가 적용된 테이블에 데이터 갱신(INSERT, UPDATE, DELETE)이 반복되다보면, 트리의 균형이 깨지면서 성능이 악화.

B+Tree

B+Tree는 B-Tree를 확장 및 개선한 자료 구조로서, 말단의 리프 노드에만 데이터의 위치(Value)를 관리.
중간 브랜치 노드에 Value가 없어서 B-Tree보다 메모리를 덜 차지하는 만큼, 노드의 메모리에 더 많은 Key를 저장가능.
리프 노드들끼리는 LinkedList 구조로 서로를 참조. 부등호(>, <)를 이용한 순차 검색 연산을 하는 경우, 많은 노드를 방문해야 하는 B-Tree에 비해 B+Tree는 말단 리프 노드를 저장한 LinkedList를 한 번만 탐색하는 등 속도 이점.