🤔 인덱스(Index)란?
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
실생활 속에서
우리는 책에서 원하는 내용을 찾기 위해서 책의 처음부터 끝가지 원하는 내용을 찾지 않는다.
- 목차나 인덱스에서 원하는 내용을 먼저 찾은 뒤 해당 내용이 있는 페이지를 찾아간다.
DB는?
데이터베이스에서도 우리와 같이 시간을 알뜰하게 쓰기 위해서 데이터와 데이터의 위치를 포함한 자료구조를 생성해서 빠르게 조회할 수 있도록 인덱스를 사용한다.
DB에서 데이터 조회 요청
DB에서 데이터 조회 요청을 하면, DB 서버 프로세스는 메모리(DB 버퍼 캐시)를 먼저 확인한다.
- 메모리에는 자주 사용되는 테이블이 캐싱되어 있는데, 메모리에 원하는 데이터가 없는 경우 디스크에서 데이터 파일을 복사해온 후 조회한 데이터를 찾아 반환한다.
인덱스를 사용하지 않으면 테이블 전체를 비교하여 탐색하는 Table Full Scan이 발생하게 된다.
하지만 항상 풀 스캔이 느린것은 아니다. 인덱스를 사용하려면 인덱스를 통해 PK를 찾고 PK를 통해 레코드를 찾는 과정이 필요하기 때문에 다.
- 옵티마이저는 인덱스를 통해 레코드 1건을 읽는 것이 테이블을 통해 직접 읽는 것 보다 4~5배 정도 비용이 더 많이 드는 것으로 예측하는데 테이블에 데이터가 별로 많지 않거나 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않는 것이 효율적이라서 옵티마이저가 인덱스를 이용하지 않고 테이블 전체를 읽어서 처리한다.
보통 조건을 검색을 하기 위해서 where문을 사용할 때 인덱스로 생성한 컬럼을 사용하면 인덱스를 사용하여 Table Full Scan을 최소화해서 조회 성능을 높일 수 있다.
- 인덱스는 데이터가 정렬되어 있기 때문
인덱스 사용 방법
- 위에 명령으로 인덱스를 만들어줄 수 있고 테이블의 PK 값으로 항상 Index가 있는데 다음 포스팅때 이야기하겠습니다.
데이터 100만개를 기준으로 email 컬럼의 index를 생성하고 생성하지 않았을 때 차이 입니다.
- 데이터를 급하게 넣다가 ㅜ email 형식이 아닌건 양해 부탁드립니당🥹
인덱스 생성해주기
이처럼 인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE에 특정 데이터를 찾아올 때 성능이 함께 향상될 수 있다.
👻 인덱스(index) 관리
- DBMS는 인덱스를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다.
빠르게 탐색하기 위해서 정렬된 상태의 인덱스를 만들었는데 Insert(삽입), Update(수정), Delete(삭제)가 수행된다면 추가적인 연산이 발생하고 그에 따른 오버헤드가 발생하게 된다.
- INSERT: 새로운 데이터에 대한 인덱스를 추가함
- DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
- UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함
내가 좋아하는 연예인 순으로 정렬해서 인덱스를 만들었는데 순위가 변경된다면?
- 배열을 정렬하는 것처럼 사이에 들어오는 요수의 개수만큼 순위가 밀리는 요소들은 전부 요소 개수만큼 뒤로 이동을 해야 한다.
간단한 예시를 들어본거지만 추가적인 연산과 그에 따른 오버헤드가 무엇인지 이해하려면 Clustered Index와 Non-clustered Index의 차이를 학습해야 한다. 여기서 순위(1,2,3)는 PK라고 생각하면 된다.
😉 인덱스(index)의 장점과 단점
장점과 단점을 이해하고 사용되지 않는 인덱스는 바로 제거하는 습관을 가지자!
장점
디스크와 버퍼풀(메모리)[Page]를 전부 돌아다니면서 찾아오는게 아니기 때문에 전반적인 시스템의 부하를 줄일 수 있으며 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- Where 절로 조건 검색을 하는 경우
- Order by 절로 정렬을 하는 경우
- min(), max()로 최소 최대 값을 구하는 경우
단점
인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
- 살짝 이야기 하면 Clustered Index는 오직 테이블을 정렬하기 때문에 별도의 저장 공간이 필요하지 않은데 Non-clustered Index는 테이블 데이터와 함께 테이블에 저장되는 것이 아니라 별도의 장소에 저장되는데 약 10%에 저장공간이 필요한 것이다.
인덱스를 관리하기 위해 추가 작업이 필요하며 인덱스를 잘못 사용할 경우 오히려 성능이 저하될 수 있다.
- CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하될 수 있다.
- UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 사용하지 않음 처리를 해주기 때문에 빈번하게 발생된다면 실제 데이터 건수보다 인덱스는 훨씬 많이 존재하게 되며 SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 된다.
🙆🏻♂️ 인덱스(index)를 사용하면 좋은 경우
인덱스를 효율적으로 사용하기 위해서는 데이터가 거의 중복되지 않는 컬럼(Cardinality가 낮음 컬럼)이나 조건절 또는 Order by 절에 자주 사용되는 컬럼을 인덱스로 생성하는 것이 좋다
1. 규모가 큰 테이블
- 규모가 작은 테이블에 인덱스를 사용할 경우 Table Full Scan과 차이가 크지 않으며 Insert, Update, Delete시 발생하는 문제들이 발목을 잡을 수 있다.
2. INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
3. JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
- 인덱스는 추가 공간이 필요하며 조건 절이 없다면 인덱스가 사용되지 않는다.
4.데이터의 중복도가 낮은 컬럼 (카디널리티가 높은 컬럼)
🤔 카디널리티(Cardinality)란?
카디널리티는 특정 데이터 집합의 유니크(Unique)한 값의 개수이다.
- 중복도가 낮으면 카디널리티가 높다고 표현한다.
- 반대로 중복도가 높으면 카디널리티가 낮다고 표현한다.
- distinct를 통해서 쉽게 구할 수 있다.
📚 인덱스(index)의 자료 구조
인덱스의 대표적인 자료구조로 해시 테이블(Hash Table)과 B+Tree가 있다.
해시 테이블
해시 테이블은 Key, Value를 한 쌍으로 데이터를 저장하는 자료구조로 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
- 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조이다.
DB 인덱스에서 해시 테이블을 이용한다면 key는 컬럼, value는 데이터의 위치로 구현하지만 실제로 인덱스에서 잘 사용하지 않는다.
- 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하게 되며 등호(=) 연산에만 최적화가 되어 있다. 따라서 부등호(<,>) 연산이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
B+Tree가 나오게 된 배경
이진 트리(Binary Tree)가 좌우 자식 간의 균형이 맞지 않을 경우에는 매우 비효율적이다. O(N)
자식 2개 만을 갖는 이진 트리(Binary Tree)를 확장하여 N개의 자식을 가질 수 있도록 고안된 B-Tree 구조를 일반적으로 사용하는데
B-Tree 역시 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다.
- 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이며 MySQL의 DB engine인 InnoDB는 B+tree로 이뤄져있다.
B+Tree
B+Tree는 모든 노드에 데이터(Value)를 저장했던 BTree와 다른 특성을 가지고 있다.
- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 자식 포인터만 저장한다.
- 리프노드들은 LinkedList로 연결되어 있다.
- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
- B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.
장점
1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다.
- 하나의 node에 더 많은 포인터를 가질 수 있어서 트리의 높이가 더 낮아지게 된다. (검색 속도 향상)
2. Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고 leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다.
- B-Tree는 모든 node를 확인해야 한다.
단점
B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 한다.
B+Tree를 사용하는 이유는?
인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다.
- B+Tree의 리프노드들을 LinkedList로 연결되어 있기 때문에 순차검색을 용이하게 하는 등 B-Tree를 인덱스에 맞게 최적화하였다.
B+Tree는 O(𝑙𝑜𝑔2𝑛log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.
InnoDB에서 사용된 B+Tree의 구조
InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다.
📚 Reference
'DB' 카테고리의 다른 글
| MySQL 트랜잭션과 잠금 (2) | 2024.05.07 |
|---|---|
| Clustered Index 와 Non-Clustered Index (1) | 2024.03.25 |
