데이터베이스에서 인덱스는 뭘까?

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

책을 예시로 들면, 책에서 원하는 내용을 찾을 떄, 책의 모든 페이지를 살펴보며 찾아 보는것은 시간이 오래 걸립니다. 그런데 보통 책을 펼쳐보면 맨 앞 혹은 맨 뒤에 색인을 추가하는데, 데이터베이스의 인덱스는 책의 색인과 같습니다. 사실 인덱스라는 단어도 책의 색인에서 온 것입니다.

데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성해서 빠르게 조회할 수 있습니다.

다음과 같은 사용자(user) 데이터베이스가 존재한다고 가정해봅시다.

name	age
강백호	23
서태웅	12
채치수	18
송태섭	52
정대만	82
권준호	90

여기서 나이가 18세 즉, age == 18인 행을 찾으려면

select * from user where age = 18;

이러한 sql 문법을 사용할 수 있을 것입니다.

그런데 age == 18인 행을 찾기 위해서는 모든 데이터페이스를 찾아보면서 직접 찾아야 할 것입니다. 왜냐하면 age == 18인 위치를 정확하게 모르기 때문입니다.

만약 사용자가 1억명이 존재하는 경우에는요?

탐색에 엄청난 시간과 리소스가 필요할 것입니다.

탐색을 효과적으로 할 수 있는 방법이 어떤 것이 존재할까요?

배열에 [ 1, 2, 3, 4, 5, ... , 99, 100] 다음과 같이 1 ~ 100의 숫자가 들어있다고 가정해봅시다. 만약 해당 배열에서 70이라는 숫자를 찾기 위해서는 어떤 방법이 가장 빠를까요? 최악의 방법은 1부터 하나하나 세어가는 것일 겁니다. 위에서 나이를 찾는것과 같이요.

우리는 보통 숫자를 찾을 때 기준을 정해서 찾곤 합니다. 예를 들어 가장 중간 값을 먼저 볼 겁니다. 위의 배열에서는 중간값은 50입니다. 따라서 다음 탐색범위는 50 ~ 100의 중간값 정도를 찾아보겠죠. 이런식으로 절반씩 줄여나가본다면 빠르게 79이라는 숫자를 찾아낼 수 있을겁니다.

그렇다면 데이터베이스 내에서도 비슷한 방법을 사용해서 탐색할 수 있지 않을까요?

그런데 이를 적용하기 위해서는 중요한 전제조건이 필요합니다. 위의 배열을 살펴보면 1 ~ 100까지 순서대로 정렬이 된 상태입니다. 즉, 이와 같이 탐색하기 위해서는 자료가 우선 정렬이 된 상태여야 합니다. 그래서 찾고자 하는 자료에 대해 정수 순서 혹은 가나다 순서로 미리 정렬이 되어있어야 합니다. 책 샀을 때, 색인을 보면 단어들이 ㄱ 부터 시작하는 것을 확인할 수 있을 겁니다. 비슷한 이유라고 생각합니다.

그래서 age 컬럼에서 데이터를 빠르게 찾고 싶다면 다음과 같이 정렬이 된 상태여야 합니다.

name	age
서태웅	12
채치수	18
강백호	23
송태섭	52
정대만	82
권준호	90

그런데 테이블 자체에서 이렇게 정렬하기엔 리소스가 아깝겠죠? name까지 같이 정렬하기도 해야하고, 새로운 값이 추가되는 경우에는 age에 기반해서 입력해야 하니까요.

age
12
18
23
52
82
90

그래서 이처럼 age만 따로 복사해서 정렬해둔 상태로 있으면 더 효과적으로 정렬할 수 있겠죠? 이렇게 정렬해둔 컬럼의 이름을 인덱스라고 부르기로 약속했습니다.

그런데 인덱스는 실제로 위와 같은 형태로 저장이 될 까요?

보통 컴퓨터 안에 있는 자료들을 저장할 때는 Array 혹은 Linked List에 담아서 저장하게 됩니다.

그런데 보통 데이터베이스들은 실제 자료를 저장할 때 나무 형태의 자료 구조를 사용하게 됩니다.

이처럼 데이터베이스에서 인덱스를 생성해달라는 요청이 들어오면 해당 자료를 위와 같은 트리 형태로 배치하게 됩니다.

이러한 트리를 Binary Search Tree라고 합니다.

위의 자료구조를 각 노드에 여러 값을 입력을 통해 성능을 향상시키면 다음과 같이 B-Tree를 구성할 수 있습니다.

더 나아가 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 아래 형태의 자료구조를 B+Tree 라고 합니다.

그림에서 확인할 수 있듯 B+Tree는 모든 노드에 데이터를 저장했던 B-Tree와 다른 특성을 가지고 있습니다. 우선 리프노드만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드들은 데이터를 위한 인덱스만 가집니다. 또한 리프노드들은 Linked List로 연결되어 있으며, 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 됩니다.

위 B+Tree는 O(logn)이라는 시간 복잡를 갖지만 이러한 특성으로 인해 인덱싱에 적합한 자료구조가 되었습니다.

실제 InnoDBDptj B+Tree는 일반적인 구조보다 더 복잡하게 구현되어 있습니다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되어 있으며, 자식 노드들은 Single Linked List로 연결이 되어있습니다.

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

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

장점

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

단점

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

만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져 성능이 오히려 저하되는 역효과가 발생할 수 있씁니다. 그러한 이융 중 하나가 DELETE와 UPDATE 연산 때문입니다. UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고, '사용하지 않음' 처리를 해준다고 했습니다. 만약 어떤 테이블에서 DELETE와 UPDATE가 빈번하게 발생된다면 실제 데이터보다 인덱스가 훨씬 많이 존재하게 되어, SQL문 처리 시 비대해진 인덱스 때문에 오히려 성능이 떨어지게 될 것입니다.

참고

• https://mangkyu.tistory.com/96
• https://www.youtube.com/watch?v=iNvYsGKelYs