1. 인덱스
인덱스는 키 값으로 행 데이터의 위치를 식별하는데 사용하는 기능입니다.
그러기 위해서는 원본 테이블을 기준으로 잘 정렬된 별도의 테이블, 즉 인덱스 테이블을 생성해야 하고, 이로 인해 데이터 엑세스 성능을 높일 수 있습니다.
인덱스를 효과적으로 사용하려면 정규화가 되어 있어야 합니다.
정규화가 되어 있지 않은 테이블은 컬럼이 많으며, 이에 따라 조합할 수 있는 인덱스가 많아지게 됩니다.
인덱스가 많으면, 갱신 성능이 나빠지고 디스크 공간도 많아지므로 인덱스를 효과적으로 사용하려면 정규화가 잘 되어 있어야 합니다.
인덱스는 어떤 경우에 사용하면 좋을까요?
인덱스(index)를 사용하면 좋은 경우
규모가 작지 않은 테이블
INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
데이터의 중복도가 낮은 컬럼
인덱스의 단점
인덱스를 사용하게 되면 검색성능이 좋아집니다.
하지만 장점이 있으면 단점도 있겠죠?
인덱스를 사용하면 다음과 같은 단점이 있습니다.
자원 소비가 많아진다.
인덱스 테이블이라는 테이블이 생성되므로 메모리를 많이 소비하게 됩니다.
따라서 PK 같은 컬럼들을 인덱싱 하도록 하고, 많은 컬럼을 인덱스로 사용하지 않도록 남용하지 않는 것이 좋습니다.SELECT를 제외한 INSERT, UPDATE, DELETE에 대한 성능 저하
어떤 테이블에 데이터를 추가할 경우, 이에 관계된 인덱스 테이블에서는 데이터를 정렬해야 하므로 전체적인 성능이 저하됩니다.
인덱스에는 어떤 알고리즘이 적용될까??
인덱스 알고리즘에는 여러가지 종류가 있습니다.
우리는 오늘 그 중에서 2가지를 살펴보도록 하겠습니다.
해시 테이블
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용합니다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조입니다
해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원합니다.
하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문입니다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않습니다.
즉, 예를 들면 "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용됩니다.
B+ 트리
- 실제 데이터가 저장된 리프노드( Leaf nodes )
- 리프노드까지의 경로 역할을 하는 논리프노드( Non-leaf nodes )
- 경로의 출발점이 되는 루트 노드( Root node )
WHERE key = 123WHERE key BETWEEN 100 AND 200
LIKE 검색의 와일드카드는 전방 일치여야 인덱스 효과를 얻을 수 있습니다.
WHERE key LIKE 'foo%'
Leaf node에서 문자열이 사전 순서대로 정렬돼 있기 때문에 전방 일치가 아닌 LIKE 검색은 물리적으로 불가능합니다.
B- Tree와 B+ Tree의 차이점
B-tree는 각 노드에 데이터가 저장됨
B+tree는 index 노드와 leaf 노드로 분리되어 저장됨
(또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)
참고
[자료구조] 그림으로 알아보는 B+Tree
정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색과 선형탐색까지 가능한 실전형 자료구조 B+ 트리입니다.
velog.io