인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 향상시키기 위한 자료 구조이다.
특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.
또한, 인덱스 생성 시 오름차순으로 정렬하기 때문에 정렬된 주소체계라고 표현할 수 있다.
데이터베이스 안의 레코드를 처음부터 풀스캔하지 않고, B+ Tree로 구성된 구조에서 Index 파일 검색으로 속도를 향상시킨다.
인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다.
해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.
인덱스의 장점의 핵심은 '데이터들이 정렬이 되어있다'는 점이다.
테이블의 레코드(row : 행)에는 내부적으로 순서가 없이 뒤죽박죽으로 저장이 된다.
이렇게 되면 WHERE 절에 특정 조건에 맞는 데이터들을 찾아낼 때, 레코드의 처음부터 끝까지 다 읽어서 비교해야 한다.
이것을 풀 테이블 스캔 (Full Table Scan), 줄여서 풀 스캔(Full Scan)이라고 한다.
하지만 인덱스 테이블 스캔(Index Table Scan) 시 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에
해당 조건에 맞는 데이터들을 빠르게 찾아낼 수 있는 것이다. 이것이 인덱스를 사용하는 가장 큰 이유이다.
인덱스를 사용하면 ORDER BY에 의한 정렬(Sort) 과정을 피할 수가 있다.
ORDER BY는 굉장히 부하가 많이 걸리는 작업이다. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생되기 때문이다.
하지만 인덱스를 사용하면 이미 정렬이 되어 있기 때문에 이러한 전반적인 자원의 소모를 하지 않아도 된다.
이것 또한 데이터가 정렬되어 있기에 얻을 수 있는 장점이다.
MIN값과 MAX값의 경우 인덱스 테이블의 시작 값과 끝 값을 가져오면 되기 때문에
풀 테이블 스캔으로 테이블을 모두 뒤져서 작업하는 것보다 훨씬 효율적으로 찾을 수 있다.
인덱스의 가장 큰 문제점은 정렬된 상태를 계속 유지시켜줘야 한다는 점이다.
그렇기에 레코드 내에 데이터 값이 바뀌는 경우, 그에 따른 오버헤드가 발생한다.
INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다.
결과적으로 인덱스 테이블, 원본 테이블 이렇게 두 군데의 데이터 수정 작업을 해줘야 한다.
그렇기 때문에 DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋다.
검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋지만 무조건 검색 시에도 인덱스가 좋은 것은 아니다.
인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 낫다.
직관적인 예시를 들자면 1개의 데이터가 있는 테이블과 100만 개의 데이터가 들어 있는 테이블이 있다고 하자.
100만 개의 데이터가 들어있는 테이블이라면 풀 스캔보다는 인덱스 스캔이 유리하겠지만, 1개의 데이터가 들어있는 테이블은 굳이 인덱스 스캔 없이 풀 스캔이 빠를 것이다.
인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다.
무턱대고 인덱스를 만들어서는 결코 안 된다는 것이다. 즉, 속도 향상에 비해 단점들의 COST를 비교해서 인덱스를 만들지 말지를 정해야 한다.
앞서 설명했듯이 인덱스는 항상 최신의 데이터를 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다.
때문에 INSERT, UPDATE, DELETE 수행 시 그에 따른 부하가 발생할 수 있는데
이러한 부하를 최소화하기 위해 '데이터 삭제' 작업 대신 '인덱스를 사용하지 않는다'는 접근 방식을 사용한다.
- INSERT : 새로운 데이터에 대한 인덱스를 추가함
- DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행
- UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 새로운 인덱스를 추가함
이렇게 '사용하지 않는다' 접근을 통해 인덱스를 업데이트하지 않는 것은 업데이트 작업에 따른 부하를 최소화하고 데이터 변경 작업을 더 효율적으로 수행할 수 있도록 도와준다.
그러나 이러한 방식을 통해 쿼리 성능이 손실될 수 있으므로 설계 시에 신중한 고려가 필요하다.
생성된 인덱스를 가장 효율적으로 사용하려면 데이터의 분포도는 최대한으로 그리고 조건절에 호출 빈도는 자주 사용되는 컬럼을 인덱스로 생성하는 것이 좋다.
인덱스는 특정 컬럼을 기준으로 생성하고 기준이 된 컬럼으로 정렬된 인덱스 테이블이 생성된다. 이 기준 컬럼은 최대한 중복이 되지 않는 값이 좋다.
가장 최선은 PK로 인덱스를 거는 것이라고 할 수 있다.
중복된 값이 없는 인덱스 테이블이 최적의 효율을 발생시키겠고, 반대로 모든 값이 같은 컬럼의 인덱스 컬럼이 된다면 인덱스로써의 가치가 없다고 봐야 할 것이다.
- 조건절에 자주 등장하는 컬럼
- 항상 = 으로 비교되는 컬럼
- 중복되는 데이터가 최소한인 컬럼 (분포도가 좋은 컬럼)
- ORDER BY 절에서 자주 사용되는 컬럼
- JOIN 조건으로 자주 사용되는 컬럼
해시 테이블은 키(Key)와 해시 값(Hash Value) 쌍으로 이루어진 자료구조이다.
O(1)의 시간복잡도를 가지고 있어 상당히 빠른 검색을 할 수 있는 것이 특징이다.
해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다.
해시테이블 기반의 DB 인덱스는 (데이터 = 컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다.
하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그 이유는 해시가 등호(=) 연산에만 특화되어있기 때문이다.
해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>,<)이 자주 사용되는 데이터베이스 검색을 위해서는 해시테이블이 적합하지 않다.
B-Tree는 데이터베이스에서 가장 널리 사용되는 인덱스 자료구조 중 하나이다.
B-Tree는 균형 잡힌 이진 검색 트리로 O(logN)의 시간 복잡도를 가지고 있다.
B-Tree의 각 노드 내 데이터들은 항상 정렬된 상태인 것이 특징이며, 하나의 노드에 여러 개의 key와 그에 대응하는 data를 가질 수 있고 최대 자식이 2개 이상(자식 노드 개수는 (n+1)을 가진다) 일 수 있다.
B-Tree 가 DB 인덱스로 선택받을 수 있었던 다른 트리와의 큰 차이점은 '노드 하나에 여러 데이터가 저장' 될 수 있다는 점이다.
(* RedBlack-Tree와의 차이를 비교해보면 이해가 쉽다)
표시된 부분을 보면 마치 배열처럼 정렬이 되어있는데, 실제 메모리 상에 차례대로 저장이 되어있다.
때문에 같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다.
이는 즉, 같은 노드 상에서 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 하는 것이다.
ex) 200 이라는 값을 탐색하는 과정
- 200이라는 값이 있는지 확인하기 위해, 100, 155, 226이 저장되어 있는 Root 노드에 있는 데이터들을 탐색한다. 실제 메모리 디스크 상 순차적으로 저장되어 있는 데이터들을 빠르게 탐색한다.
- Root 노드에 200이 없다. 200은 155와 226 사이의 값이므로, 해당 범위에 존재하는 자식 노드를 가리키는 포인터가 존재하는지 확인한다. 있으면 포인터를 통해 해당 자식 노드로 접근한다. 자식 노드는 168, 200의 값을 가지고 있다.
- 실제 메모리 디스크 상 순차적으로 저장되어 있는 168, 200의 값을 빠르게 탐색한다. 찾으려 했던 200의 값을 찾아낸다.
결론적으로 DB 인덱스로 B-Tree가 가장 적합한 이유들을 정리하면 아래와 같다.
- 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
- 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
- 데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
B+tree는 B-tree의 확장개념으로, B-tree의 경우, internal 또는 branch 노드에 key와 data를 담을 수 있다.
하지만, B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.
리프 노드 사이를 Link (Pointer)로 연결하여 B-Tree에 비하여 쉬운 순회가 가능하도록 만든점이 B+ Tree의 특징이다.
B+tree의 장점
-
리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
-
풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.
Reference
[DB] 데이터베이스(DB) 인덱스(Index) 란 무엇인가?
[DB] 데이터베이스 인덱스(index) 개념 정리
[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)
데이터베이스 인덱스는 왜 'B-Tree'를 선택하였는가 <-⭐ 한번씩 읽어보면 좋은 글
B-Tree, B+ Tree