index
인덱스는 DBMS의 저장 성능을 희생하고 검색 성능을 높이기 위해 만들어진 자료 구조입니다. 일부 저장공간을 사용하지만 풀 스캔 방식에 비해 빠르게 데이터를 처리할 수 있기 때문에 유용하게 쓰일 수 있습니다.
연산에 따른 인덱스 작업
INSERT: 새로운 데이터에 대한 인덱스를 추가함
DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함
UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 수 있다.
MangKyu's Diary:티스토리
index 자료 구조
hashtable
Key-Value 형태로 데이터를 저장하는 자료구조입니다. 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 제공합니다. 데이터 탐색 시 해시 함수(Hash Function)를 이용해 Key에 해당하는 index 값을 구합니다. index를 이용하여 배열에 저장된 value에 접근하기 때문에 해시 테이블의 평균 시간복잡도는 O(1)입니다.
해시가 등호(=) 연산에만 특화되었기 때문에 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않습니다.
B-Tree
이진트리와 형태는 비슷하지만 한 노드 당 자식 노드가 2개 이상 가능한 자료구조입니다.
-
최상위 노드를 루트 노드라고 합니다.
-
중간에 위치한 노드들을 브랜치 노드라고 합니다.
-
맨 말단에 위치한 노드를 리프 노드라고 합니다.
-
하나의 노드에 매달린 자식 노드는 2개 이상 가능합니다.
-
Key-Value 값들은 Key를 기준으로 항상 오름차순으로 정렬되어 있습니다.
B-Tree는 균형트리라서 이론적으로는 모든 데이터에 대해서 같은 속도로 결과를 얻습니다. 하지만 만약 잦은 UPDATE와 DELETE 등으로 균일성이 깨진다면 데이터를 얻는 속도에 차이가 있을 수 있습니다.
B+Tree
B+tree는 B-tree의 확장개념입니다. B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.
- 리프 노드들은 LinkedList 구조로 서로를 참조하고 있으므로 B-Tree에 비해 노드 순회가 쉽습니다.
- 브랜치 노드와 리프 노드에 모두 Key가 존재하므로 Key 중복이 발생합니다.
- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만 갖고 있습니다.
B+Tree B-Tree차이점
자세히 알아보기
특징
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있습니다.
- 전반적인 시스템의 부하를 줄일 수 있습니다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장 공간이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있습니다.
기타
인덱스 종류
- 알고리즘 별
- B-Tree
- hash
- 역할 별
- 클러스터 인덱스
- 비클러슽 인덱스
- 데이터 허용 여부
- 유니크 인덱스
- 논유니크 인덱스
인덱스 활용
- 규모가 작지 않은 테이블
- INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
- 데이터의 중복도가 낮은 컬럼 (카디널리티가 높은 컬럼)
카디널리티(cardinality)
상대적으로 데이터가 중복되지 않는 정도
주의
- INSERT, UPDATE, DELETE 작업이 자주 일어나는 컬럼에는 인덱스를 사용하지 않는 것이 좋습니다.
- WHERE 절에 자주 사용되는 컬럼이 있다면, 인덱스를 부여할 지 고민해 봅니다.
모든 컬럼을 왜 인덱스에 넣으면 안되나요?
인덱스는 검색 조회를 위한 용도로 데이터베이스에 할당된 메모리를 소모합니다. 최적의 조건이 아닌 모든 컬럼을 인덱스에 넣게 되면 불필요한 메모리 낭비가 발생합니다.
또한, 인덱스는 키 값에 따라 리프 노드의 위치가 결정되므로 키 값을 마음대로 바꿀 수 없습니다. 그래서 기존 키는 삭제 마크만 해 놓고 새로운 키를 삽입하게 되는데, 한 레코드의 컬럼들이 통째로 바뀌게 되면 마킹하고 새로 넣어야 할 키가 많아지게 됩니다.
