[DB] Index

Index (인덱스)?

인덱스는 데이터베이스의 테이블에 대한 검색 속도를 높여주는 자료구조입니다. 특정컬럼에 대한 인덱스를 생성하면 해당 컬럼의 데이터들이 정렬되어 별도의 메모리공간에 물리적주소와 함께 저장됩니다. 따라서 해당 컬럼에 where 조건 등을 걸어 접근할 경우 이를 활용할 수 있게 되어 접근 속도가 빨라집니다. 하지만 생성에 시간이 걸리고 INSERT, UPDATE, DELETE가 자주 발생하는 경우 성능이 하락할 수 있습니다. 일반적으로 하나의 컬럼을 key로 인덱스를 생성하지만, 여러개의 컬럼을 key로 인덱스를 생성하는 composite index라는 개념도 존재합니다.

 

Index의 자료구조

이러한 인덱스를 구현하는 자료구조로는 대표적으로 해시테이블과 B+ Tree가 있습니다. 자료구조 자체에 대한 설명은 최소화했습니다.

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

해시테이블을 활용한 인덱스는 정확히 하나만 탐색하는 equality search에는 유용하게 사용할 수 있지만, 여러 범위를 탐색하는 range search에는 사용할 수 없습니다. 해시테이블은 해시함수를 사용하기 때문에 값이 조금이라도 달라지면 완전히 다른 해시값을 생성하기 때문입니다.

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

B+ Tree를 활용한 인덱스는 equality search 성능이 해시테이블에 비해 조금 떨어지지만 range search가 가능하다는 장점이 있습니다. B+ Tree는 해당하는 컬럼의 모든 데이터 주소를 리프노드에 저장하며 나머지 노드는 방향설정을 위한 데이터 값만을 가지고 있습니다. 그리고 리프노드들끼리는 링크드리스트로 연결되어 있습니다. 따라서 특정 범위의 끝 부분에 해당하는 리프노드에만 접근하면 링크드리스트를 이용해 쉽게 그 범위에 해당하는 모든 데이터의 주소에 접근할 수 있는 것입니다.

 

Primary Index와 Secondary Index

특정 key로 primary index가 설정되면 실질적 데이터 테이블 구조도 그에 맞게 정렬됩니다. 따라서 하나의 테이블당 하나만 primary index를 가집니다. primary index는 데이터가 clustered되어 있기 때문에 range search를 해도 범위의 모든 값에 대해 I/O를 수행하지 않아서 빠른 처리가 가능합니다.

하지만 secondary index는 실질적 테이블의 구조를 정렬하지 않습니다. 따라서 하나의 테이블당 여러개의 secondary index를 가질 수 있습니다. 하지만 range search를 수행할 경우 각 데이터의 값에 대해 모두 I/O를 수행해야하기 때문에 좋은 성능을 낼 수 없습니다.