[DB] 인덱스(Index)

-목차-

1. 인덱스(Index)란?

    1.1 배경

2. 인덱스의 관리

    2.1 인덱스의 장단점

    2.2 인덱스 사용시 고려사항

3. 인덱스의 자료구조

    3.1 해시테이블

    3.2 B Tree

    3.3 B+ Tree

마치며

1. 인덱스(Index)란?

인덱스란 추가적인 쓰기 작업과 저장공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

인덱스를 사용하는 목적은 RDBMS에서 검색 속도를 높이기 위함이라 할 수 있다.

• 테이블의 Column을 색인화 한다.(따로 파일로 저장)
• 해당 테이블의 레코드를 full scan(완전 탐색)하지 않는다.
• (B+ 트리 구조로)색인화된  Index 파일 검색으로 검색 속도 향상

 

1.1 배경

인덱스는 책의 목차에 주로 비유됨

하지만 일반적인 책을 생각해보면 목차가 문자열 순으로 되어있지는 않다. 

문자열 순이 아닌 책의 내용 순으로, 주요 타이틀을 기준으로 목차를 만든다.

목차가 없는 것보다는 더 편리하지만, 책의 주요 내용을 가나다 순으로 정리한 목록이 있으면, 내가 원하는 특정내용을 더 찾기 쉬울 것이다.

어느정도 두꺼운 책에서는 색인(역색인 - 책의 맨뒤에 단어 가나다순 목록과 등장하는 페이지 적어놓은것)이라는 것을 제공해서 바로 이러한 편의성을 제공한다.

이때 색인은 영어로 Index이며, DB의 Index와 완전히 동일한 기능을 한다.

 

예시

다음 테이블을 보자

서점에 진열된 책들의 이름, 카테고리, 위치를 저장한 테이블이다.
10000권의 책이 있고, A~Z까지 랜덤한 위치에 진열되어있다.

 

어떤 사람이 서점에 방문해 카테고리가 java인 책을 모두 구매하려한다.

카테고리가 java인 책의 이름과 위치를 전부 찾기위해 다음과 같이 쿼리했다.

테이블 명은 book_store이다.

 

SELECT name, location
FROM book_store
WHERE category = 'java'

 

결과는 아래와 같다.

name		 location
let’s start java	A
let’s start java	C
java? java!		Z
javavara		K

 

현재 인덱스가 없기 때문에, 1000개의 데이터를 모두 뒤져서 결과를 찾았을 것이다. (full scan)

category를 기준으로 데이터를 찾고있기 때문에, category에 대한 인덱스를 생성하고, category를 기준으로 인덱스 정렬하자 그리고 DB가 쉽게 찾아갈 수 있도록 rowid를 같이 넣어주자.

category	id
…		…
C++		10000
…	…
java		1
java		4
java		4222
java		9999
javascript	3
…		…
python		2
python		4223
…		…

 

인덱스는 문자열 순서대로 정렬되어있기 때문에,

'java'라는 문자열을 계속 검색하다가 'javascript'라는 문자열을 만나는 순간, 이제 더이상 'java'라는 문자열을 존재하지 않는다고 탐색을 종료할 수 있다.

게다가 내부적으로 데이터를 B-Tree라는 구조에 저장하기 때문에, 'java'라는 문자열을 찾아낼 때 맨 처음부터 순차적으로 조회하는 것보다 훨씬 빠르다.

그리고 찾아낸 rowid값을 기준으로 데이터베이스에 조회하면 그만이다.

인덱스에서 찾아낸 rowid값은 1, 4, 4222, 9999 이므로 다음과 같이 검색하면 된다.

SELECT name, location
FROM book_store
WHERE row_id IN (1, 4, 4222, 9999)

 

book_store 테이블에서 row_id가 1, 4, 4222, 9999인 책의 이름과 위치를 조회하는 쿼리이다.

이때 category = 'java'로 검색하는 것과 무슨 차이가 있을까 의문이 생길 수 있다.

row_id는 사실 데이터를 삽입할 때 DB 내부에서 자동적으로 생성하는 값으로, 해당 row(행)의 고유한 주소값을 가리킨다.

따라서 rowid가 주어지면 DB는 해당 데이터의 위치가 어디있는지 일일이 찾지 않아도 rowid를 통해 바로 접근할 수 있다.

정리하면 이 rowid를 통한 검색은 DB에서 가장 빠르게 데이터를 찾아낼 수 있는 검색 방법이라는 사실을 알고있으면 된다.

 

즉, 인덱스를 만드는 이유는 바로 이 rowid를 기준으로 데이터를 탐색할 수 있도록 유도해서 쿼리의 성능을 향상시키기 위함이다.

 

실제 사용시에는 이러한 일련의 과정을 사용자가 직접 입력할 필요없이 다음과 같이 인덱스를 생성해놓으면 내부적으로 알아서 작동한다.

CREATE INDEX index_category ON book_store(category)

 

위와 같이 book_store 테이블의 category 컬럼에 index_category라는 인덱스를 생성한 후, 기존과 똑같이 사용하면 된다. (그럼 내부적으로 위에서 작업했던 과정이 수행되면서 성능 향상된다.)

SELECT name, location
FROM book_store
WHERE category = 'java'

 

인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 그러한 이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.

 

---

2. 인덱스의 관리

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

그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해줘야하며, 그에 따른 오버헤드가 발생한다.

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

 

2.1 인덱스의 장단점

장점

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

단점

• 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
• 인덱스를 관리하기위해 추가 작업이 필요하다.
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

만약 INSERT, DELETE, UPDATE (DML) 가 빈번한 속성(column)에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.
그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문이다. 앞에서 설명한대로 UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 "사용하지 않음"처리를 해준다. 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만, 인덱스는 100만건이 넘어가게 되어, SQL문 처리시 비대해진 인덱스에의해 오히려 성능이 떨어지게 될 것이다.

그렇다면 인덱스를 사용하기에 적합한 경우는 어떠한 경우이고, 고려해야 할 사항은 무엇이 있을까?

 

2.2 인덱스 사용시 고려사항

먼저 인덱스를 사용하기에 적합한 경우는 아래와 같다.

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼 (고유한 값 위주로)
• 기타 등등

인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그렇기 때문에 사용하지 않는 인덱스는 바로 제거를 해주어야한다.

 

카디널리티

중복도가 ‘낮으면’ 카디널리티가 ‘높다’고 표현한다.

중복도가 ‘높으면’ 카디널리티가 ‘낮다’고 표현한다.

카디널리티는 전체 행에 대한 특정 컬럼의 중복 수치를 나타내는 지표이다.

 

카디널리티가 높을 수록 인덱스 설정에 좋은 컬럼
= 한 컬럼이 갖고있는 값의 중복 정도가 낮을 수록 좋다.

 

컬럼에 인덱스를 걸 때, 내가 원하는 데이터를 선택하는 과정에서 최대한 많은 데이터가 걸러져야 성능이 좋을 것이다
(선택하는 데이터가 많아질수록 full scan에 가까워지므로)

즉, 여러 컬럼을 동시에 인덱싱할 때, 카디널리티가 높은 컬럼(중복이 적은 컬럼을) 우선순위로 두는 것이 인덱싱 전략에 유리하다.

예를 들면 users 테이블에 인덱스를 걸어보자
(테이블의 여러 컬럼이 결합해 하나의 인덱스를 이루는 경우, 이를 결합인덱스라고 한다. 결합인덱스는 컬럼의 순서에 따라 엑세스하는 범위가 달라지므로 유의해야한다.)

CREATE INDEX idx_location_first ON users(location, name, id);
CREATE INDEX idx_id_first ON users(id, name, location);

 

전자의 경우 location (카디널리티가 낮은 컬럼 : 중복도가 높은 컬럼)을 우선적으로 인덱싱했고,

후자의 경우 id (카디널리티가 높은 컬럼 : 중복도 낮은 컬럼)을 우선적으로 인덱싱했다.

전자는 인덱스 정의한 순서대로 location -> name -> id 순으로 값을 필터링한다.

후자는 id-> name -> location 순으로 필터링한다.

앞에서 필터링할 때 먼저 많이 걸러줄수록 뒤에서 탐색해야하는 범위가 줄어드므로 카디널리티 높은 항목을 우선적으로 적용하는 것이 좋다.

 

---

3. 인덱스의 자료구조

인덱스를 구현하기 위한 자료구조는 여러가지가 있다.
대표적으로 해시테이블과 B+ Tree가 있다.

 

3.1 해시테이블

해시테이블은 key, value로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.

 

해시테이블 기반의 DB 인덱스는 (데이터 = 컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그 이유는 해시가 등호(=) 연산에만 특화되어있기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>,<)이 자주 사용되는 데이터베이스 검색을 위해서는 해시테이블이 적합하지 않다.

즉, 예를들어 "나는"으로 "시작하는"(부등호연산) 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀받지 못하게된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+ Tree가 일반적으로 사용된다.

 

3.2 B Tree

이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화시킨 것이 B-Tree

자식 수에 대한 일반화를 진행하면서 하나의 레벨에 더 저장되는 것 뿐만아니라 트리의 균형을 자동으로 맞춰주는 로직까지 가지고 있는 트리이다. 단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리이다.

따라서 균형잡힌 확장된 이진 탐색트리이므로 시간복잡도 O(logN)이 보장된다.

 

대량의 데이터를 처리해야할 때 검색구조의 경우 하나의 노드에 많은 데이터를 저장할 수 있는 것은 상당히 큰 장점이다.
대량의 데이터는 메모리보다 블럭단위로 입출력하는 하드디스크 or SSD에 저장해야하기 때문이다.
ex) 한 블럭이 1024 바이트면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용이 발생하기 때문. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있다면 입출력에 있어서 효율적인 구성을 갖출 수 있다.

 

규칙

• 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 한다
• 노드의 자료수가 N이면, 자식수는 N+1이어야 한다.
• 각 노드의 자료는 정렬된 상태여야한다.
• 루트노드는 적어도 2개 이상의 자식을 가져야한다.
• 루트노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고있어야한다.
• 외부 노드로 가는 경로의 길이는 모두 같다.
• 입력 자료는 중복될 수 없다.

 

3.3 B+ Tree

B+ Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+ Tree는 모든 노드에 데이터(Value)를 저장했던 B Tree와 다른 특성을 가지고 있다.

• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
• 리프노드들은 LinkedList로 연결되어있다.
• 데이터노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 B Tree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 B Tree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 B Tree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

이러한 이유로 B+ Tree는 O(log2N)의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

 

B Tree와 B+ Tree에 대해서는 이후 자세하게 다뤄 보도록 하겠다.

 

---

마치며

• 인덱스는 데이터가 저장된 물리적 구조와 밀접한 관계가 잇다.
• 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다.
• 레코드의 삽입과 삭제가 빈번하게 일어나는 경우, 인덱스의 개수를 최소로 하는 것이 효율적이다.
• 인덱스가 없으면 특정한 값을 찾기위해 모든 데이터 페이지를 확인하는 TABlE SCAN이 발생한다.
• 기본키를 위한 인덱스를 기본 인덱스라 하고, 기본 인덱스가 아닌 인덱스들을 보조 인덱스라고 한다. 대부분의 관계형 데이터베이스 관리 시스템에서는 모든 기본키에 대해서 자동적으로 기본 인덱스를 생성한다.
• 레코드의 물리적 순서가 인덱스의 엔트리 순서와 일치하게 유지되도록 구성하는 인덱스를 클러스터드 인덱스라고 한다.

 

클러스터(Cluster)란 여러 개를 하나로 묶는다는 의미로 주로 사용되는데, 클러스터드 인덱스도 크게 다르지 않다. 인덱스에서 클러스터드는 비슷한 것들을 묶어서 저장하는 형태로 구현되는데, 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 여기서 비슷한 값들은 물리적으로 인접한 장소에 저장되어 있는 데이터들을 말한다.
클러스터드 인덱스는 테이블의 프라이머리 키에 대해서만 적용되는 내용이다. 즉 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터드 인덱스라고 표현한다. 클러스터드 인덱스에서는 프라이머리 키 값에 의해 레코드의 저장 위치가 결정되며 프라이머리 키 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 한다. 그렇기 때문에 프라이머리 키를 신중하게 결정하고 클러스터드 인덱스를 사용해야 한다.
클러스터드 인덱스는 테이블 당 한 개만 생성할 수 있다. 프라이머리 키에 대해서만 적용되기 때문이다, 이에 반해 non 클러스터드 인덱스는 테이블 당 여러 개를 생성할 수 있다.

 

클러스터드 인덱스

• 인덱스 키의 순서에 따라 데이터가 물리적으로도 정렬되어 저장되는 방식
• 실제 데이터가 순서대로 저장되어 있어 인덱스를 검색하지 않아도 원하는 데이터를 빠르게 찾을 수 있다.
• 데이터 삽입, 삭제 발생 시 순서를 유지하기 위해 데이터를 재정렬해야한다.
• 한 개의 릴레이션에 하나의 인덱스만 생성 가능

넌클러스터드 인덱스

• 인덱스의 키 값만 정렬되어 있을 뿐 실제 데이터는 정렬되지 않는 방식
• 데이터를 검색하기 위해서는 먼저 인덱스를 검색하여 실제 데이터 위치를 확인해야 하므로 클러스터드 인덱스에 비해 검색 속도가 떨어진다.
• 한 개의 릴레이션에 여러 인덱스를 만들 수 있다.

---

참고 자료

https://velog.io/@syleemk/인덱스

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database