데이터베이스 - 인덱스

인덱스란 무엇인가?

인덱스란 책으로 비유하자면, 목차와 같다.

만약, 책에 읽고 싶은 특정한 장이 있다고 생각해보자 어떻게 찾아가겠는가?

책을 다 넘기고나서 ‘아 여기가 내가 읽고 싶어하는 장이다!’ 하면서 찾겠는가?

아니면 책 맨 첫페이지에 있는 목차를 살펴보고 한 번에 찾아서 보겠는가?

나라면 후자를 선택할 것이다. (물론 책에 목차에 비유하기는 했지만, 책에도 Index가 따로 있다.)

왜 사용하는가?

인덱스는 위에서 이야기 했드시 내가 원하는 데이터를 빠르게 찾기위해서 사용된다.

어떻게 찾는가?

아래 학생 테이블이 있다고 가정하자.

• student

id	student_no	name	age
1	1732	hong	23
2	1456	kim	22
3	1445	rang	20
4	1325	lee	25
5	1689	joo	24
6	1156	dong	21
7	1789	dong	21
8	1698	dong	24

SELECT * FROM student WHERE name = 'lee';

인덱스가 걸려 있지 않는다면 첫번째 데이터부터 이름이 맞는지 확인해가면서 찾아 갈 것이다. (=full scan)

데이터가 있는 만큼 순차적으로 찾아나가기 때문에 최악의 시간은 O(N)이 걸린다고 할 수 있다.

하지만, 인덱스가 걸려있다면 어떻게 될까?

• index table student(name)

이렇게 인덱스 테이블이 만들어진다.

이름과 포인터라는 데이터가 생기고 포인터는 실제 테이블의 튜플 데이터를 가르키게된다.

데이터를 조회한다면 어떻게 조회를 하게 될까?

위의 쿼리에서 lee라는 이름의 데이터를 조회하고 싶었기 때문에 BinarySearch를 통해 조회를 하게 된다.

때문에 데이터를 찾는 시간은 최악의 경우 O(logN)만큼의 시간이 걸리게 된다.

BinarySearch란?

데이터는 정렬되어있다.

1. 찾고자하는 값을 중앙과 비교한다.
2. 중앙의 값과 같다면 그 값이 찾고자 하는 값이다.
3. 중앙보다 작다면 왼쪽에 찾고자하는 값이 있기에 다시 1번으로 돌아간다.
4. 중앙보다 크다면 오른쪽에 찾고자하는 값이 있기에 다시 1번으로 돌아간다.

예를 들어 찾고자하는 값이 7이고 다음과 같이 데이터가 있다고 가정하겠다.

find_number = 7
numbers = [1, 2, 3, 4, 5, 6, 8]

찾고자하는 값과 중앙값을 비교한다. 찾고자하는 값이 중앙값보다 크기 때문에 4를 포함한 왼쪽 데이터를 제외하고 다시 중앙값을 찾는다.

다시 찾고자하는 값과 중앙값을 비교한다. 찾고자하는 값이 중앙값보다 크기 때문에 6을 포함한 왼쪽 데이터를 제외하고 다시 중앙값을 찾는다.

다시 찾고자하는 값과 중앙값을 비교한다. 찾고자하는 값과 일치하기 때문에 3번이라는 비교만에 데이터를 찾게 되었다. O(log_28) = 3

다시 돌아와서 아래의 쿼리를 조회한다고 가정해보자

SELECT * FROM student WHERE name = 'dong' AND age = 21;

지금 현재 name에는 인덱스가 걸려있다. 그렇다면 위의 절차와 같이 조회를 하게 될까?

정답은 아니다.

name에만 인덱스가 걸려있어 name은 빠르게 찾을 수 있지만, age는 해당 테이블의 데이터를 확인하여 찾고자하는 age와 같은지 판단해야한다.

그렇다면 age에 인덱스를 걸면 될까?

정답은 아니다.

결과적으로 name인덱스나 age인덱스만 사용하게 될 것이다.

그렇다면 어떻게 해야할까?

복합인덱스 (Composite Index)

복합 인덱스란 여러 개의 컬럼을 함께 인덱스로 거는 것이다.

복합인덱스는 인덱스를 걸 첫번째 대상을 기준으로 정렬한다.

• name, age => name을 기준으로 정렬

SELECT * FROM student WHERE name = 'dong' AND age = 21;

이 쿼리의 맞는 데이터를 찾는다면 첫번째 name에서 BinarySearch를 통해 찾고, 두번째 age에서 인덱스의 값과 같은지 비교하여 찾는다.