Index

인덱스

DBMS에 대한 검색 속도를 향상시켜주는 자료구조이다.

🗣 DBMS: 데이터베이스 관리 시스템은 데이터베이스에 적재된 데이터 작업을 수행할 뿐만 아니라 데이터베이스를 보호하고 보안을 제공한다. 데이터베이스 관리 시스템의 기능은 크게 구성(정의), 조작, 제어 기능으로 나눌 수 있다.

DBMS는 데이터를 순차적으로 쌓으므로, 특정 데이터를 찾기 위해서는 데이터의 FULL-SCAN인 순차 탐색이 필요하다.

DBMS는 특정 데이터를 특별한 자료 구조로 쌓아 탐색 속도를 개선할 수 있는 기능을 제공한다. 해당 기능을 인덱스라 부르고 쌓은 데이터들을 인덱스 테이블이라 부른다.

인덱스를 책에서의 목차라고 생각하면 이해하기 쉽다. 책에서 원하는 내용을 찾을 때 목차나 색인을 이용하면 훨씬 빠르게 찾을 수 잇듯이 테이블에서 원하는 데이터를 찾기 위해 인덱스를 이용하면 빠르게 찾을 수 있다. 그러므로 데이터=책의 내용, 인덱스=책의 목차, 물리적 주소=책의 페이지 번호 라고 생각하면 된다.

DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 그 대신 읽기 속도를 높이는 기능이다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 칼럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져서 오히려 역효과만 불러올 수 있다.

인덱스의 관리

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

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

인덱스 테이블

인덱스 테이블은 데이터를 조회할 때 사용되는 특정 컬럼의 데이터로 구성된다. 인덱스 테이블에 포함된 데이터를 WHERE 문으로 조회하면 인덱스 테이블을 통해 ROW-ID를 빠르게 구한 뒤 단번에 행 데이터를 조회할 수 있다.

인덱스 테이블 탐색

인덱스 테이블의 핵심은 빠른 조회 성능이다. 이를 위해 인덱스 테이블은 탐색 트리 자료구조 중 하나만 B + Tree 자료 구조로 데이터를 저장한다. 탐색 트리는 O(log_2Nlog2N) 성능의 빠른 조회를 할 수 있는 특징이 있다. 그렇기에 데이터 FULL-SCAN[O(N)] 성능에 비해, 압도적인 빠른 조회를 할 수 있다는 장점이 있다.

인덱스 테이블 생성

TABLE을 생성 할 때, PK를 지정한 컬럼은 자동적으로 PK를 기준으로 인덱스 테이블이 생성된다.

만약 다른 컬럼을 인덱스 테이블을 생성하고 싶다면, 직접 생성해야한다.

인덱스의 자료구조

인덱스는 여러 자료구조를 이용해 구현할 수 있다. 대표적인 자료구조로 해시 테이블과 B + Tree가 있다.

해시 테이블(Hash Table)

해시 테이블은 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장하는 자료구조이다. 하지만 해시 테이블은실제로 인덱스에서 잘 사용하지 않는다.

컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만 값을 변행해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

B + Tree 인덱스 알고리즘

일반적으로 사용되는 인덱스 알고리즘은 B + Tree 알고리즘이다. B +- Tree 인덱스는 칼럼의 값을 변형하지 않고(사실 값의 앞부분만 잘라서 관리), 원래의 값을 이용해 인덱싱하는 알고리즘이다.

• Node는 데이터가 존재하는 공간이다.
• Leaf Node만 인덱스(key)와 함께 데이터(Value)를 가지고 있고, 나머지 Root Node와 Branch Node는 데이터를 위한 인덱스(Key)만을 갖는다.
• Leaf Node에만 데이터를 저장하고 Leaf Node들끼리 LinkedList로 연결되어 있 선형 시가이 소모되어 시간 효율이 올라간다.
• Root Node에서 경로를 확인 후, 그에 알맞는 Node들로 이동하여 최종적으로 원하는 데이터가 있는 Leaf Node에 도달한다.

index를 생성하는데 B + Tree를 사용하는 이유

데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적이다고 생각할 수 있다. SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. hash table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조에 적합하지 않다.

인덱스의 장단점

장점: 인덱스를 사용하는 이유

🗣 데이터가 정렬되어 있기 때문에 테이블에서 검색과 속도를 향상시킨다.

• 조건 검색 Where절의 효율성: 보통 Where절의 사용할 때 특정 조건에 맞는 데이터를 찾기 위해 데이터를 처음부터 끝까지 다 비교해야 하는데, 인덱스를 통해 데이터가 정렬되어 있으면 빠르게 찾아낼 수 있다.
• 정렬 Order by 정의 효율성: 인덱스를 사용하면 Order by에 의한 Sort 과정을 피할 수 있다. 본래 Order by는 굉장히 부하가 많이 걸리는 작업이기 때문에 인덱스를 통해 이미 정렬되어 있으면 부하가 걸리지 않을 수 있다.
• MIN, MAX의 효율적인 처리가 가능: 이것또한 인덱스를 통해 데이터가 정렬되어 있기 때문에 처음부터 끝까지 뒤져서 찾느 것이 아닌 인덱스로 정렬된 데이터에서 MIN, MAX를 효율적으로 추출할 수 있다.

🗣 인덱스를 사용하면 테이블 행의 고유성을 강화시킬 수 있다.

🗣 시스템의 전반적인 부하를 줄일 수 있다.

단점: 인덱스 사용시 주의할 점

🗣 인덱스의 가장 큰 문제점은 정렬된 상태를 계속 유지시켜야 한다는 점이다.

인덱스가 적용된 컬럼에 정렬을 변경시키는 INSERT, UPDATE, DELETE 명령어가 수행된다면 게속 정렬을 해줘야해서 그에 따른 부하가 발생한다. 이런 부하를 최소화하기 위해 인덱스는 데이터 삭제하는 개념에서 인덱스를 사용하지 않는다 라는 작업으로 이를 대신한다.

🗣 무조건 인덱스 스캔이 좋은 것은 아니다.

검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋지만 무조건 인덱스가 검색에좋은 것은 아니다. 예를 들어, 1개의 데이터가 있는 테이블과 100만개의 데이터가 들어 있는 테이블이 있다고 하면, 100만 개의 데이터가 들어있는 테이블이라면 풀 스캔보다는 인덱스 스캔이 유리하겠지만, 1개의 데이터가 들어있는 테이블은 인덱스 스캔보다 풀 스캔이 더 빠르다.

🗣 속도 향상을 위해 인덱스를 많이 만드는 것이 좋지 않다.

인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다. 때문에 너무 많이 인덱스를 생성하면 하나의 쿼리문을 빠르게 만들 수 있지만 대신에 전체적인 데이터베이스의 성능 부하를 추래한다. 때문에 무조건적인 인덱스 생성보다 SQL문을 효율적으로 짜고, 인덱스 생성은 마지막 수단으로 사용해야 한다.