개발자 성장 기록 50 - 인덱스(Index)

인덱스(index)란?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

 

우리가 백과사전에서 원하는 정보를 찾기 위해서 맨 첫 장부터 하나씩 찾아가게 된다면 오랜 시간이 걸리기 때문에 책의 맨 앞에 색인을 추가하는데, 데이터베이스의 인덱스는 이 색인과 같다.

 

이처럼 데이터베이스에서 인덱스를 사용하면, 데이터를 검색할 때 전체 테이블을 스캔(Full Scan)하는 것이 아니라, 인덱스를 사용하여 검색 대상 레코드의 범위를 줄일 수 있다. 이는 대량의 데이터를 다루는 경우 데이터 검색 속도를 크게 향상시킨다.

 

인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 그 이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.

그림1. Index

---

인덱스의 장단점

장점

1. 검색 대상 레코드의 범위를 줄여 검색 속도를 빠르게 할 수 있다.
2. 중복 데이터를 방지하거나 특정 칼럼의 유일성을 보장할 수 있다.
3. ORDER BY 절과 GROUP BY 절, WHERE 절 등이 사용되는 작업이 더욱 효율적으로 처리된다.

단점

1. 인덱스 생성에 따른 추가적인 저장 공간이 필요하다. (인덱스 사용 시 해당 정보를 담은 MYI 파일 생성)
2. CREATE, DELETE, UPDATE 작업 시에도 인덱스를 업데이트해야 하므로 성능 저하가 발생할 수 있다.
3. 한 페이지를 동시에 수정할 수 있는 병행성이 줄어든다.
4. 인덱스 생성 시간이 오래 걸릴 수 있다.

---

인덱스는 데이터베이스에서 검색 및 처리하는 속도를 향상시키는 데 중요한 역할을 한다. 하지만 인덱스를 적절하게 활용하지 않으면 오히려 데이터베이스의 성능이 저하되거나 저장 공간이 낭비될 수 있다.

따라서, 인덱스를 적절히 선택하고 생성하는 것이 중요하다.

---

인덱스의 관리

인덱스는 항상 최신 데이터를 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 따라서 인덱스가 적용된 칼럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며, 그에 따른 오버헤드가 발생한다.

• INSERT : 새로운 데이터에 대한 인덱스를 추가한다.
• DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행한다.
• UPDATE : 기존의 인덱스를 사용하지 않도록 처리하고, 갱신된 데이터에 대해 인덱스를 추가한다.

---

인덱스를 사용하는 경우

1. 대량의 데이터를 검색하는 경우

대량의 데이터를 검색해야 하는 경우에는 인덱스를 사용하여 검색 속도를 향상시킬 수 있다.

대량의 데이털르 전체 스캔하는 것(Full Scan)하는 것은 매우 느리고 부하가 발생하기 때문에 이 경우에 인덱스를 사용하여 검색하는 것이 효율적이다.

 

2. 정렬된 결과를 출력하는 경우

인덱스를 사용하여 데이터를 정렬하면 매우 빠르게 정렬된 결과를 출력할 수 있다.

따라서 데이터를 정렬하는 경우에는 인덱스를 사용하는 것이 좋다.

 

3. 조인 연산을 수행하는 경우

조인 연산을 수행하는 경우에는 인덱스를 사용하여 연산 속도를 향상시킬 수 있다.

인덱스를 생성하여 조인 대상 테이블의 데이터를 빠르게 검색하는 것이 좋다.

 

4. 유니크한 값을 가져오는 경우

인덱스는 유니크한 값을 가지고 있는 필드에 대해 중복되지 않는 값을 빠르게 검색할 수 있다.

이러한 경우 인덱스를 사용하여 검색 속도를 빠르게 할 수 있다.

 

5. 검색 빈도가 높은 경우

검색 빈도가 높은 필드에 대해서 인덱스를 생성하여 검색 속도를 향상시키는 것이 좋다.

---

인덱스의 자료구조

해시 테이블(Hash Table)

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로, O(1)의 시간복잡도를 가지고 있어 빠른 데이터 검색이 필요할 때 유용하다.

그림2. Hash Table

해시 테이블의 검색 방식은 Key를 해시 함수를 사용하여 해시 값으로 변환한 후, 해당 해시 값에 해당하는 값을 찾아서 검색한다.

검색 속도가 빠르지만 데이터의 분포에 따라 충돌이 발생할 수 있으므로 충돌을 해결하기 위한 방법이 필요하다.

 

또한, 해시는 등호(=) 연산에만 특화되어 있어 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

(이전에 작성한 Hash Table 관련 포스팅을 참고하면 좋을 것 같다.)

개발자 취준 기록 34 - Hash(Table·Map·Set)

---

B-Tree

B-Tree는 데이터베이스에서 가장 널리 사용되는 인덱스 자료구조 중 하나이다. O(logN)의 시간 복잡도를 가지고 있으며, 균형 잡힌(Balanced) 이진 검색 트리로 검색 속도를 높이기 위해 사용된다.

그림3. B-Tree

 

B-Tree는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가질 수 있다.

최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 한다.

 

B-Tree의 각 노드 내 데이터들은 항상 정렬된 상태인 것이 특징이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. (자식 노드의 개수는 n+1개)

또한, 한 노드에서 여러 개의 Key를 가질 수 있고, Key에 해당하는 데이터도 함께 갖고 있다.

---

B+Tree

B-Tree는 어떤 한 데이터의 검색에서는 빠를 수 있으나, 모든 데이터를 순회하기 위해서는 Leaf Node까지 갔다가 다시 부모 Node로 BackTracking하여 트리의 모든 Node를 방문해야 하므로 비효율적이다.

이러한 단점을 보완한 것이 B+Tree이다.

 

B+Tree는 B-Tree의 변형된 구조로 몇 가지 차이점을 가지고 있다. B+Tree 또한 균형 잡힌 이진 검색 트리이며, B-Tree에 비해 더 많은 Key를 가질 수 있다.

그림4. MySQL에서 쓰이는 인덱스인 B+Tree 구조

 

B+Tree는 Internal Node(내부 노드)와 Leaf Node(단말 노드)로 구분된다.

B+Tree의 모든 데이터는 Leaf Node에서만 저장되며, Internal Node에는 검색을 위한 인덱스만 저장된다.

 

모든 Leaf Node가 Linked List로 연결되어 있으며, 순차적으로 저장되어 있다는 특징이 있다.

Full Scan시, Linked List로 연결되 Leaf Node들에 대해서만 읽기를 진행하면 되므로 시간이 단축되기 때문에 범위 검색이나 순차 검색에 효율적이다.

---

참고

https://ittrue.tistory.com/331

https://mangkyu.tistory.com/96