[TIL] 자료구조 : Database Index

은경·2022년 2월 8일

TIL db 자료구조

[data structure]자료구조

목록 보기

6/7

1. 인덱스(Index)의 개념

데이터베이스 테이블에 대한 검색 속도를 향상 시켜주는 자료구조.

책의 목차 또는 색인과 같은 개념.

테이블의 모든 데이터를 검색하면 시간이 오래 걸림 -> 데이터와 데이터의 위치를 포함한 자료구조를 생성, 빠르게 조회할 수 있다.

DBMS는 인덱스를 항상 최신의 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다.

INSERT: 신규 데이터에 대한 인덱스를 추가

DELETE: 삭제하는 데이터의 인덱스를 더이상 사용하지 않게 해야함.

UPDATE: 기존의 인덱스는 사용하지 않고, 갱신된 데이터에 대해 인덱스를 추가함.

2. Index의 특징

가장 큰 특징은 테이블의 데이터들이 정렬이 되어있다는 점. 이 특징으로 인해 조건 검색이라는 영역에서 굉장한 장점을 가짐.

데이터가 쌓일 수록 레코드 내부는 순서가 뒤죽박죽으로 저장되는데,
이렇게 되면 WHERE절에 특정 조건에 맞는 데이터를 검색할 때 풀 테이블 스캔(Full Table Scan)으로 레코드의 처음부터 끝까지 데이터를 다 읽어서 검색 조건과 비교를 한다.
하지만 인덱스 테이블은 데이터들이 정렬되어 있기 때문에 해당 조건(WHERE)에 맞는 데이터를 빠르게 찾아낸다.

장점

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

단점

인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 따로 필요함.
인덱스 관리를 위한 추가 작업 필요 -> 정렬된 상태를 계속 유지시켜 줘야함.
인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
-> INSERT, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져 오히려 성능이 저하됨 : UPDATE와 DELETE는 기존의 인덱스를 삭제하는 것이 아닌 [사용하지 않음] 처리를 하기 때문.

3. Index의 효율적인 사용

규모가 작지 않은 테이블
INSERT, DELETE, UPDATE가 빈번하지 않은 컬럼
JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼
데이터의 중복도가 낮은 (분포도가 좋은) 컬럼

4. Index의 자료구조

대표적인 자료구조로는 해시 테이블과 B+Tree가 있다.

해시 테이블 (Hash Table)

Key, Value로 데이터를 저장, Key값으로 고유한 Index생성 후 저장 된 값을 꺼내옴
빠른 데이터 검색, 시간복잡도 O(1)
등호(=) 연산에만 특화되어 있다.
- 해시함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하기 때문
- 부등호 연산(<,>)이 자주 사용되는 데이터베이스 검색에는 적합하지 않음.
- ex) 오늘은 으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 받지 못함.

B+Tree

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있음 (기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조)

자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조. (2개 이하면 이진트리)
리프노드(데이터 노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
리프노드들은 연결리스트(Linked List)로 연결되어 있다 -> 순차검색 용이
데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
O(log n)의 시간복잡도를 갖지만 해시 테이블보다 인덱싱에 적합.
- B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 하는 단점을 가짐.