Database - Index
What is Index?
추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료 구조. 모든 테이블의 Record(Row)를 하나 하나 찾아 보면 당연히 시간이 오래 걸리므로, 특정 칼럼값의 데이터와 데이터의 위치를 알려주는 포인트를 쌍으로 해서 Index(인덱스)에 저장해 주는 것이다.
이렇게 인덱스를 사용할 경우 시간을 단축할 수는 있지만, 추가적인 저장공간이 필요하고(해쉬 개념의 어쩔 수 없는 숙명), 새로운 쿼리에 대해 인덱스에도 그 결과를 업데이트 시키는 연산을 해주어야하므로 오버헤드가 발생하게 된다.
따라서 인덱스는 JOIN, WHERE, ORDER BY 등이 자주 사용되면서도 INSERT나 UPDATE, DELETE가 잘 발생하지 않는 컬럼이면 좋고, 데이터의 크기도 커서 Full Scan시 굉장히 오래걸리는 테이블에서 생성하는 것이 좋다.
자료구조
Index에 많이 사용되는 자료구조를 알아보자.
B+tree
가장 일반적으로 사용되는 알고리즘이다. B-tree 알고리즘의 확장 개념으로 용어가 다르니 헷갈리지 말아야 한다. 먼저, B-tree는 Self-Balancing tree 자료구조로 Binary 트리와 같은 방식으로 Search하게 되며, 차이점이라면 두개 이상의 Children을 갖을 수 있다. 이때 Self-Balancing의 의미는 모든 Leaf(Branch가 아닌 끝 노드)가 거의 균일한 Depth, 탐색 시간을 갖는 것을 말한다.
이제 B+tree로 돌아가 보자. B-tree에서는 branch 노드에 Key와 Data를 담을 수 있었지만, B+tree에서는 브랜치 노드에서는 Key만 넣고, Data는 담지 않으며, 오직 Leaf 노드에서 Key와 Data를 저장하고 리프 노드끼리는 Linked List로 연결되어 있다.
따라서, B+tree는 Branch 노드에 Data를 담지 않아서 메모리를 더 확보 가능하여 더 많은 Key를 수용할 수 있으며 하나의 노드에 더 많은 Key를 담을 수 있기에 트리 전체의 높이가 낮아지게 된다. 또한, 풀 스캔 시 리프노드에 모든 Data를 포함하고 있으므로, 이 Leaf Node로 된 Linked List에 대한 탐색만 이루어지면 되기 때문에 모든 노드를 검색해야하는 B-tree 보다 이점을 갖는다.
Hash
데이터, 데이터의 위치를 Key, Value 값으로 사용하여 칼럼의 값(데이터)으로 생성된 해시를 통해 인덱스를 구현한다. 해시 테이블의 시간 복잡도는 O(1)이므로 매우 빠른 검색을 지원한다.
하지만, DB 인덱스에서 해시의 사용은 제한적인데, 그 이유는 해시가 등호(==) 연산에만 특화되어 있기 때문이다. 즉, 부등호 연산(<, >)이 자주 사용되는 데이터 베이트 검색에서는 해시를 사용할 수 없게 된다.
종합해보면 Hash가 O(1)으로 빠른 접근이 가능하지만, 부등호 연산이 불가능한 단점이 있어 O(logN)의 시간 복잡도를 갖는 B+tree가 많이 쓰인다.