테이블 인덱싱이란?
인덱싱은 데이터베이스 테이블의 컬럼의 값과 해당 레코드가 저장된 주소를 키/값 형태로 저장해 두는 것을 말합니다. 특정 값을 찾고자 할때 정렬되어 있는 인덱스를 통해 빠르게 찾고자 하는 값으로 갈 수 있습니다. 여기서 중요한 사실은 인덱스는 항상 정렬되어 있다는 것입니다.
인덱스는 SortedList 와 마찬가지로 저장되는 컬럼의 값을 이용해 항상 정렬된 상태를 유지합니다. 반면 데이터 파일은 ArrayList 와 같이 저장된 순서대로 별도의 정렬 없이 그대로 저장해 둡니다. 인덱스는 Trade-off 관계가 성립합니다. 인덱스가 많은 테이블은 INSERT, UPDATE, DELETE 명령어의 처리 속도를 느리게 만들지만, SELECT 명령의 성능을 향상 시킵니다.
인덱스가 없는 컬럼을 조건으로 UPDATE, DELETE 를 하게 되면 굉장히 느려 많은 양의 데이터를 삭제해야 하는 상황에선 인덱스로 지정된 컬럼을 기준으로 진행하는 것을 추천합니다.
인덱스의 장점과 단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있습니다.
- 전반적인 시스템의 부하를 줄일 수 있습니다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요합니다.
- 인덱스를 관리하기 위해 추가 작업이 필요합니다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있습니다.
만약 CREATE, DELETE, UPDATE 가 빈번한 속성에 인덱스를 걸게 되면, 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있습니다. 이러한 이유 중 하나는 DELETE 와 UPDATE 연산 때문입니다. 앞에서 설명한대로 UPDATE 와 DELETE 는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 합니다. 만약 어떤 테이블에 UPDATE 와 DELETE 가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만건이 넘어가게 되어 SQL 문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어질 수 있습니다.
인덱스를 사용하면 좋은 경우
- 규모가 작지 않은 테이블
INSERT,UPDATE,DELETE가 자주 발생하지 않는 컬럼JOIN이나WHERE또는ORDER BY에 자주 사용되는 컬럼- 데이터의 중복도가 낮은 컬럼
인덱스의 자료구조
인덱스를 구현하기 위해서는 여러가지 자료구조를 사용할 수 있습니다. 아래에서는 가장 대표적인 해시테이블과 B+Tree에 대해서 알아보도록 하겠습니다.
해시 테이블 (Hash Table)
해시 테이블은 {Key : Value} 형태로 데이터를 저장하는 자료구조 중 하나입니다. 주로 빠른 데이터 검색이 필요할 때 유용합니다. 해시 테이블은 Key 값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조입니다.
해시 테이블 기반의 DB인덱스는 {데이터 : 컬럼의 값, 데이터의 위치} 를 {Key : Value}로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현합니다. 해시 테이블의 시간 복잡도는 O(1) 이며 매우 빠른 검색을 지원합니다.
하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적입니다. 이유는 해시가 등호 연산에만 특화되어 있기 때문입니다. 해시 함수는 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않습니다. 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용됩니다.
B+Tree
B+Tree 는 DB에 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조 입니다.
B+Tree는 아래와 같은 특징을 가지고 있습니다.
- Leaf Node 만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드(Index)들은 데이터를 위한 인덱스만을 가집니다.
- Leaf Node들은 LinkedList로 연결되어 있습니다.
- Data Node 크기는 Index Node의 크기와 같지 않아도 됩니다.
데이터 베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있습니다. 이러한 이유로 BTree의 Leaf Node 들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화 하였습니다.
이러한 이유로 B+Tree는 O(log_2 n)의 시간 복잡도를 가지고 있지만 해시테이블 보다 인덱싱에 더욱 적합한 자료구조입니다.
Reference
