13. 인덱스란?

인덱스란?

많은 사람이 인덱스를 언급할 때는 항상 책의 제일 끝에 있는 찾아보기(또는 "색인")로 설명하곤 한다. 책의 마지막에 있는 "찾아보기"가 인덱스에 비유된다면 책의 내용은 데이터 파일에 해당한다고 볼 수 있다. 책의 찾아보기를 통해 알아낼 수 있는 페이지 번호는 데이터 파일에 저장된 레코드의 주소에 비유될 것이다. DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다. 그래서 칼럼(또는 칼럼들)의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key-value pair)으로 인덱스를 만들어 두는 것이다. 그리고 책의 "찾아보기"와 DBMS의 인덱스의 공통점 가운데 중요한 것이 바로 정렬이다. 책의 찾아보기도 내용이 많아지면 우리가 원하는 검색어를 찾아내는 데 시간이 걸릴 것이다. 그래서 최대한 빠르게 찾아낼 수 있게 "ㄱ", "ㄴ", "ㄷ"...와 같은 순서대로 정렬돼 있는데, DBMS의 인덱스도 마찬가지로 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

인덱스의 또 다른 특성을 설명하고자 이제는 프로그래밍 언어의 자료구조로 인덱스와 데이터 파일을 비교해 가면서 살펴보자. 프로그래밍 언어별로 각 자료구조의 이름이 조금씩 다르긴 하지만 SortedList와 ArrayList라는 자료구조는 익숙할 정도로 많이 들어본 적이 있을 것이다. SortedList는 DBMS의 인덱스와 같은 자료구조이며, ArrayList는 데이터 파일과 같은 자료구조를 사용한다. SortedList는 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조이며, ArrayList는 값을 저장되는 순서대로 그대로 유지하는 자료구조다. DBMS의 인덱스도 SortedList와 마찬가지로 저장되는 칼럼의 값을 이용해 하상 정렬된 상태로 유지한다. 데이터 파일은 ArrayList와 같이 저장된 순서대로 별도의 정렬 없이 그대로 저장해 둔다.

그러면 이제 SortedList의 장점과 단점을 통해 인덱스의 장점과 단점을 살펴보자. SortedList 자료구조는 데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있다. DBMS의 인덱스도 인덱스가 많은 테이블은 당연히 INSERT나 UDPATE 그리고 DELETE 문장의 처리가 느려진다. 하지만 이미 정렬된 "찾아보기"용 표(인덱스)를 가지고 있기 때문에 SELECT 문장은 매우 바르게 처리할 수 있다.

결론적으로 DBMS에서 인덱스는 데이터의 저장(INSERT, UDPATE, DELETE) 성능을 희생하고 그 대신 데이터를 읽기 속도를 높이는 기능이다. 여기서도 알 수 있듯이 테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지의 여부에 따라 결정돼야 한다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 칼럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져서 오히려 역효과만 불러올 수 있다.

인덱스는 데이터를 관리하는 방식(알고리즘)과 중복 값의 허용 여부 등에 따라 여러 가지로 나눠 볼 수 있다. 인덱스를 역할별로 구분해 본다면 프라이머리 키(Primary key)와 보조 키(Secondary key)로 구분해 볼 수 있다.

• 프라이머리 키는 이미 잘 알려져 있는 것처럼 그 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스를 의미한다. 이 칼럼(때로는 칼럼의 조합)은 테이블에서 해당 레코드를 식별할 수 있는 기준값이 되기 때문에 우리는 이를 식별자라고도 부른다. 프라이머리 키는 NULL 값을 허용하지 않으며 중복을 허용하지 않는 것이 특징이다.

• 프라이머리 키를 제외한 나머지 모든 인덱스는 보조 인덱스(Secondary Index)로 분류한다. 유니크 인덱스는 프라이머리 키와 성격이 비슷하고 프라이머리 키를 대체해서 사용할 수 있다고 해서 대체 키라고도 하는데, 별도로 분류하기도 하고 그냥 보조 인덱스로 분류하기도 한다.

데이터 저장 방식(알고리즘)별로 구분하는 것은 사실 상당히 많은 분류가 가능하겠지만 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다. 그리고 최근 새롭게 Fractal-Tree 인덱스와 같은 알고리즘도 도입됐다. 물론 이 이외에도 수많은 알고리즘이 존재하지만 대표적으로 시중의 RDBMS에서 많이 사용하는 알고리즘은 이 정도일 것이다.

• B-Tree 알고리즘은 가장 일반적으로 사용되는 인덱스 알고리즘으로서, 상당히 오래전에 도입된 알고리즘이며 그만큼 성숙해진 상태다. B-Tree 인덱스는 칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘이다.

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

• Fractal-Tree 알고리즘은 B-Tree의 단점을 보완하기 위해 고안된 알고리즘이다. 값을 변형하지 않고 인덱싱하며 범용적인 목적으로 사용할 수 있다는 측면에서 B-Tree와 거의 비슷하지만 데이터가 저장되거나 삭제될 때 처리 비용을 상당히 줄일 수 있게 설계된 것이 특징이다. 아직 B-Tree 알고리즘만큼 안정적이고 성숙되진 않았지만 아마도 조만간 B-Tree 인덱스의 상당 부분을 대체할 수 있지 않을까 생각한다.

데이터의 중복 여부로 구분하면 유니크 인덱스(Unique)와 유니크하지 않은 인덱스(Non-Unique)로 구분할 수 있다. 인덱스가 유니크한지 아닌지는 단순하게 같은 값이 1개만 존재하는지 1개 이상 존재할 수 있는지를 의미하지만 실제 DBMS의 쿼리를 실행해야 하는 옵티마이저에게는 상당히 중요한 문제가 된다. 유니크 인덱스에 대해 동등 조건(Equal, =)으로 검색한다는 것은 항상 1건의 레코드만 찾으면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려 주는 효과를 낸다. 이뿐만 아니라 유니크 인덱스로 인한 MySQL의 처리 방식의 변화나 차이점은 상당히 많다.

또한 인덱스를 기능별로 분류해 본다면 전문 검색용 인덱스와 공간 검색용 인덱스 등을 예로 들 수 있을 것이다. 물론 이 밖에도 수없이 많은 인덱스가 있겠지만 MySQL을 사용할 때는 이 두 가지만으로도 충분할 것이다.

참고

• Real MySQL