[DB] Index - 개념, 장단점, 자료구조(B-Tree, B+Tree)

Benjamin·2022년 8월 18일

DB

목록 보기

5/8

Index

DB의 테이블에 대한 검색 속도를 향상시켜주는 자료구조
테이블의 특정 컬럼에 인덱스 생성 : 해당 컬럼의 데이터를 정렬한 후, 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.
컬럼의 값과 물리적 주소가 (key,value)의 한 쌍으로 저장된다.

데이터 = 책의 내용 | 인덱스 = 책의 목차 | 물리적 주소 = 책의 페이지 번호

이미지 출처

Index 장단점

장점

테이블 검색 속도와 성능 향상(SELECT)
UPDATE, DELETE 성능도 함께 향상 (해당 연산을 수행하려면 해당 대상을 조회해야 하므로)

*핵심 = 인덱스에 의해 데이터들이 정렬된 형태를 갖는다는 것!
기존 : Where문으로 특정 조건 데이터 찾기위해 테이블의 전체를 조건과 비교해야하는 '풀 테이블 스캔'작업 수행 -> 인덱스 사용 : 데이터 정렬 되어있어서 조건에 맞는 데이터 빠르게 찾을 수 있음

단점

인덱스를 관리하기 위한 추가 작업 필요
추가 저장공간 필요 (DB의 약 10%에 해당하는 저장공간 필요)
잘못 사용하는 경우 오히려 성능 저하 발생

인덱스가 적용된 컬럼에 Insert, Delete, Update 작업 수행 시 추가작업 필요.

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

이처럼 데이터의 수정이 잦은 경우 성능이 오히려 낮아진다.
또한, 데이터 인덱스를 제거하는 것이 아니라 '사용하지 않음'으로 처리하고 남겨두기에 수정 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점이 발생할 수 있다.
추가 저장 공간이 많이 필요하게 되는것이다.

전체 데이터의 10~15% 이상의 데이터를 처리하거나, 데이터 RANGE가 적거나, 데이터 형식에 따라 오히려 성능이 낮아질 수 있다.
EX) 나이나 성별은 RANGE가 적은 컬럼이므로, 인덱스로 관리할 경우 인덱스를 읽고나서 다시 해당 데이터를 조회해야 하기 때문에 비효율적이다.

Index를 사용하면 좋은 경우

규모가 큰 테이블
데이터의 range가 넓고, 중복도가 낮은 컬럼
조회가 많거나 정렬된 상태가 유용한 컬럼
INSERT, UPDATE, DELETE 작업이 자주 발생하지 않는 컬럼
WHERE나 ORDER BY, JOIN 등이 자주 사용되는 컬럼

Index의 자료구조

인덱스 구현에는 다양한 자료구조를 사용할 수 있는데, 가장 대표적인 해시 테이블과 B+Tree에 대해 알아보자.

해시 테이블(Hash Table)
(key, value)로 데이터를 저장하는 자료구조
빠른 데이터 검색이 필요할 때 유용
key값을 이용해 고유한 index를 생성하여, 그 index에 저장된 값을 꺼내오는 구조
평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조

인덱스는 (key,value) = (컬럼의 값, 데이터 위치)로 구현하는데, 해시테이블은 실제로 잘 사용되지 않는다.
Why? 해시 테이블은 등호(=) 연산에 최적화되어있기 때문이다. DB내에서는 부등호(<,>)연산이 자주 사용되는데, 해시 테이블내의 데이터들은 정렬되어있지 않으므로 특정 기준보다 크거나 작은 값을 빠른시간내에 찾을 수 없다.
B+Tree
DB인덱스 위해, 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조
: 기존의 B-Tree는 어느 한 데이터의 검색은 효율적이나 모든 데이터를 한 번 순회하는데에는 트리의 모든 노드를 방문해야 하므로 비효율적. 이것을 개선한것이 B+Tree

B+Tree는 오직 leaf node에만 데이터 저장. 나머지 노드에는 자식 포인터만 저장.
leaf node끼리는 Linked list로 연결되어 있다.

장점
1. leaf node에만 데이터 저장하므로 메모리 확보. -> 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색속도 높일 수 있음.
2. Full Scan의 경우 leaf node에만 데이터 저장되어있고, 이들이 Linked List로 연결되어있어 선형 시간이 소모됨.

단점

반드시 특정 key에 접근하기 위해서 leaf node까지 가야한다. (B-Tree는 최상의 경우 특정 key를 root node에서 찾을 수 있다)

인덱스에서는 왜 B-Tree가 아닌, B+Tree를 주로 이용할까?

인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생한다.
-> B+Tree의 Linked List를 이용하면 효율적인 순차 검색이 가능.

B+Tree의 SELECT, INSERT, DELETE

B+Tree의 SELECT는 B-Tree와 동일.

INSERT

key의 수가 최대보다 적은 leaf node에 삽입하는 경우
해당 node의 가장 앞이 아닌 곳에 삽입되는 경우는 단순히 삽입.
하지만, leaf node의 가장 앞에 삽입되는 경우는, 해당 node를 가리키는 부모 node의 포인터의 오른쪽에 위치한 key를 K로 바꿔준다. 그리고 leaf node끼리 Linked list로 이어줘야 하므로 삽입된 key에 Linked list로 연결한다.

랜덤 I/O 그리고 순차 I/O
일단 랜덤 I/O가 일어나면 원하는 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽어오는 작업이 발생한다. 그럼 순차 I/O 는 어떨까?

순차 I/O 도 마찬가지로 원하는 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽어오는 작업이 발생한다.

그런데 두 읽기 방식에는 어떤 차이가 있을까?

바로 System Call 을 몇번 하는가에 차이가 있다.

위에 보이는 그림과 같이 3개의 데이터를 메모리에 담기 위해서 순차 I/O 는 시스템콜을 한번 불렀지만