[DB] Index

Dayeon myeong·2021년 3월 26일

Database

DATABASE

목록 보기

1/1

DB의 인덱스란

인덱스는 책의 색인과 같은 역할을 하는 데이터베이스 객체로써, 데이터 베이스 테이블의 검색 속도를 향상시켜줄 수 있는 자료구조이며,

칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만든다.

또한, 테이블과는 독립적으로 존재하지만, 테이블에 의존적이기 때문에 해당 테이블이 삭제될 경우 같이 제거된다.

DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 데는 빠르지만 새로운 값을 추가,삭제,수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높인다.

DB에서 자료를 검색하는 두 가지 방법

FTS(Full Table Scan) : 테이블을 처음부터 끝까지 검색하는 방법
Index Scan : 인덱스를 검색하여 해당 자료의 테이블을 액세스하는 방법

만약 Index를 적용하지 않은 컬럼을 조회한다면, 전체를 탐색하는 Full Table Scan이 수행된다. 이는 전체를 탐색하기 때문에 처리 속도가 떨어진다.

Index 자료 구조

B+ Tree 인덱스

B+Tree는 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조.

B- Tree가 모든 노드에 데이터를 저장했다면 B+ Tree는 리프노드만이 인덱스와 함께 데이터를 가지고 있고 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(Key)만을 가진다는 차이가 있다. 또한, 리프노드들이 LinkedList로 연결되어 있어서 부등호 연산을 이용한 순차 검색에 용이하다.

B+Tree의 시간 복잡도 O(logN)

B- Tree 인덱스

일반적으로 사용되는 인덱스 알고리즘으로 balanced tree를 사용. (편향된 트리가 아니도록 밸런스 유지)

칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘.

Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원.

해시 테이블 단점

값을 변형해서 인덱싱하므로 특정 문자로 시작하는 값으로 검색하는 전방 일치와 같이 값의 일부만으로 검색할 때는 사용 불가하다.
부등호 연산(>,<)이 자주 사용되는 검색에는 적합하지 않음 : 해시 함수는 등호 (=) 연산에만 특화되었다. 해시 테이블에서는 부등호(<,>)와 같이 특정 기준보다 크거나 작은 값을 찾을 수 없다.

왜 B- 트리를 사용하는가

해시테이블은 데이터 탐색 시 시간복잡도가 O(1)로 매우 빠르다. 하지만, 해시 테이블은 부등호(<, >)를 이용한 연속적인 데이터의 순차 검색이 불가능하다.

인덱스의 관리

DBMS는 인덱스를 항상 최신의 정렬된 상태로 유지시킨다.데이터의 수정, 삽입,삭제 시 다음과 같은 연산을 추가적으로 해주며 그에 따른 오버헤드가 발생한다.

INSERT : 새로운 데이터에 대한 인덱스를 추가
DELETE : 인덱스에 존재하는 값은 삭제하지 않고, 사용하지 않는다는 표시를 남김(row의 수가 그대로)
UPDATE : 이전 인덱스를 사용하지 않는다고 표시를 남기고, 갱신된 데이터에 대해 인덱스를 추가함

인덱스의 장점과 단점

장점

테이블 검색 속도를 향상 시킴
매번 테이블을 스캔한 후 행을 정렬하는 절차를 생략 : DB는 기본적으로 모든 행을 스캔하고 정렬한 뒤 일치하는 행을 필터링하여 결과를 반환, 인덱스를 사용한다면 미리 정렬된 목록을 제공함으로써 매 쿼리마다 정렬을 하지 않아도 빠른 검색이 가능.

단점

인덱스는 DB 내에서 별도의 저장 공간을 차지
데이터의 수정(insert, update, delete)가 발생할 때마다 연관 index도 업데이트해야함. 즉, 다른 쿼리의 성능이 떨어진다.
인덱스를 잘못 사용할 경우 성능이 저하될 수 있다. : 수정 삭제 삽입이 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 오히려 성능이 저하된다.