Chanhae Oh

빅데이터, 분석

인덱스 간단 정리


인덱스란?


책의 마지막에 있는 “찾아보기”가 인덱스에 비유 된다면 책의 내용은 데이터 파일에 해당. 책의 찾아보기를 통해 알아낼 수 있는 페이지 번호는 데이터 파일에 저장된 레코드의 주소에 비유될 것. DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래걸린다. 그래서 컬럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍(key-value pair)으로 삼아 인덱스를 만들어 둔다. 책의 “찾아보기”와 DBMS 인덱스의 공통점 가운제 중요한 것이 바로 정렬이다.



SortedList VS ArrayList


SortedList는 DBMS 의 인덱스와 같은 자료 구조이며, ArrayList는 데이터 파일과 같은 자료 구조를 사용한다.

SortedList : 저장되는 값을 항상 정렬된 상태로 유지하는 자료 구조 ArrayList : 값을 저장되는 순서 그대로 유지하는 자료 구조


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


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



인덱스 종류


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

키(Key)라는 말과 인덱스(Index)는 같은 의미로 사용


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


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


데이터 저장 방식(알고리즘)은 상당히 많은 분류가 있지만 대표적으로 B-Tree, Hash 인덱스로 구분할 수 있다. 그리고 최근에는 Fractal-Tree, 로그 기반의 Merge-Tree 인덱스와 같은 알고리즘을 사용하는 DBMS도 개발되고 있다.


  • B-Tree 알고리즘은 가장 일반적으로 사용되는 인덱스 알고리즘. 상당히 오래전에 도입되 알고리즘이며 그만큼 성숙해진 상태. B-Tree 인덱스는 컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘. MySQL 서버에서는 위치 기반 검색을 지원하기 위한 R-Tree 인덱스 알고리즘도 있지만, 결국 R-Tree 인덱스는 B-Tree 의 응용 알고리즘으로 볼 수 있다.

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


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