[데이터베이스] 인덱스

인덱스 (Index)

[인덱스란?]

데이터 베이스 인덱스는 추가적인 쓰기 작업과 저장공간을 활용하여 데이터베이스 테이블에 저장된 데이터의 검색 속도를 향상시키기 위한 자료구조 이다.
인덱스는 데이터베이스 내의 특정 컬럼(열), 컬럼들의 조합에 대한 값과 해당 값이 저장된 레코드(행)의 위치를 매핑하여 데이터 베이스 쿼리의 성능을 최적화하는 데 중요한 역할을 한다.

예를 들어 책에서 원하는 내용을 찾는다고 가정해보자. 책의 모든 페이지를 넘겨서 원하는 내용이 나올 때까지 찾는 것보단 목차 or 저자가 남긴 색인(index)을 통해 찾는 것이 더욱 효율적이며 빠를 것이다. 데이터베이스의 인덱스가 책의 목차와 색인과 같은 역할을 한다.
이처럼 데이터베이스에서 인덱스를 사용하면, 데이터를 검색할 떄 전체 테이블을 스캔하는 것이 아니라, 인덱스를 사용하여 검색대상 레코드이 범위를 줄일 수 있다. 이는 대량의 데이터를 다루는 경우 검색속도를 크게 향상시킨다.

[인덱스의 장단점]

장점

1. 검색 대상 레코드의 범위를 줄여 검색 속도를 향상

2. 중복 데이터를 방지하거나 특정 컬럼의 유일성(unique)을 보장

3. ORDER BY 절과 GROUP BY, WHERE 절등이 사용되는 작업이 더욱 더 효율적 처리된디.

단점

1. 인덱스 생성에 따른 추가적인 저장 공간 필요

2. INSERT(삽입), DELETE(삭제), UPDATE(수정) 작업 시에도 인덱스를 업데이트해야 하므로 성능 저하가 발생할 수 있다.

3. 한 페이지를 동시에 수정할 수 있는 병행성이 줄어든다

4. 인덱스 생성 시간이 오래 걸릴 수 있다.

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

[인덱스의 관리]

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

1. INSERT : 새로운 데이터에 대한 인덱스를 추가한다.

2. DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행한다.

3. UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가한다.

💡 [인덱스를 사용하는 경우]

1. 대량의 데이터를 검색하는 경우
대량의 데이터를 검색해야 하는 경우에는 인덱스를 사용하여 검색 속도를 향상시킬 수 있다. 대량의 데이터를 전체 스캔하는 것은 매우 느리고 부하가 발생하기 때문에 이 경우에 인덱스를 사용하여 검색하는 것이 효율적이다.

2. 정렬된 결과를 출력하는 경우
인덱스를 사용하여 데이터를 정렬하면 매우 빠르게 정렬된 결과를 출력할 수 있다. 따라서 데이터를 정렬하는 경우에는 인덱스를 사용하는 것이 좋다.

3. 조인 연산을 수행하는 경우
조인 연산을 수행하는 경우에는 인덱스를 사용하여 연산 속도를 향상시킬 수 있다. 인덱스를 생성하여 조인 대상 테이블의 데이터를 빠르게 검색하는 것이 좋다.

4. 유니크한 값을 가져오는 경우
인덱스는 유니크한 값을 가지고 있는 필드에 대해 중복되지 않는 값을 빠르게 검색할 수 있다. 이러한 경우 인덱스를 사용하여 검색 속도를 빠르게 할 수 있다.

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

[인덱스의 자료구조]

1. 해시 테이블(Hash table)

해시 테이블은 키(Key)와 해시 값(Hash Value) 쌍으로 이루어진 자료구조이다. O(1)의 시간복잡도를 가지고 있어 상당히 빠른 검색을 할 수 있는 것이 특징이다.

해시 테이블의 검색 방식은 키를 해시 함수를 사용하여 해시 값으로 변환한 후, 해당 해시 값에 해당하는 값을 찾아서 검색한다. 해시 테이블은 검색 속도가 매우 빠르지만, 데이터의 분포에 따라 충돌이 발생할 수 있다. 따라서 충돌을 해결하기 위한 방법이 필요하다.

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

2. B-Tree

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

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

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

3. B+Tree

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

B+Tree는 B-Tree와 달리 내부 노드(Internal node)와 단말 노드(Leaf node)로 구분된다. B+Tree의 모든 데이터는 단말 노드에서만 저장되며, 내부 노드에는 검색을 위한 인덱스만 저장된다.

모든 리프 노드가 연결 리스트로 연결되어 있으며, 순차적으로 저장되어 있다. 이러한 특징으로 인해 범위 검색(Range Search)이나 순차 검색(Sequential Search)에 효율적이다.

정리

💡 Index에 대해 설명해주시고, 장/단점에 대해 아는대로 말해주세요.

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

  • 예를들어, DB를 책으로 비유하면 데이터는 책의 내용일 것이고, 데이터가 저장된 레코드의 주소는 index 목록에 있는 페이지 번호일 것이다.

• 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 검색하는데 빠르지만, 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려집니다.

• 즉, 인덱스는 데이터의 저장 성능을 희생하고 그대신 데이터의 검색 속도를 높이는 기능이라 할 수 있습니다.

💡 그렇다면 DBMS는 Index를 어떻게 관리하고 있나요? (Index 자료구조)

• B+Tree 인덱스 자료구조

  • 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이며,

  • BTree 리프노드들을 LinkedList로 연결하여 순차 검색을 용이하게 합니다. 해시 테이블보다 나쁜 O(log2N)의 시간복잡도를 갖지만 일반적으로 사용되는 자료구조입니다.

• 해시 테이블

  • 컬럼의 값으로 생성된 해시를 기반으로 인덱스를 구현합니다.

  • 시간복잡도가 O(1)이라 검색이 매우 빠릅니다.

  • 부등호(<,>)와 같은 연속적인 데이터를 위한 순차 검색이 불가능하기 때문에 사용에 적합하지 않습니다.

참고

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Database/%5BDB%5D%20Index.md
https://ittrue.tistory.com/331