Index 알아보기

서론

지난 글에서 검색 성능을 향상 시키면서 index를 사용해 봤다.
index를 좀더 자세히 알아보도록하자!

인덱스란 ?

데이터베이스에서 데이터를 더 빠르게 검색하기 위해 사용하는 자료구조 이다.

테이블의 특정 열(컬럼)에 대한 포인터를 생성해, 전체 데이터를 순차적으로 검색하지 않아도 필요한 데이터를 빠르게 찾을 수 있도록 도와준다.

인덱스가 빠른 이유

1. 데이터를 정렬된 상태로 유지 -> 이진 탐색 가능

• 인덱스는 b+tree 같은 정렬된 자료구조를 사용하여 데이터를 저장한다.
• 따라서 검색할 때 이진탐색을 수행하여 O(log N)의 속도로 원하는 데이터를 찾을 수 있다.
• 반면, 인덱스가 없으면 모든행을 하나씩 탐색하는 Full Table Scan이 필요하다. 이때 시간 복잡도는 O(n)이다.

2. 특정 칼럼만 빠르게 조회 가능 -> 전체 테이블을 읽지 않음

• 인덱스는 특정 칼럼의 값 + 포인터(해당 행의 위치 정보)를 저장한다.
• 따라서 검색할 때 전체 테이블을 읽을 필요 없이 인덱스만 탐색하여 위치를 바로 찾을 수 있다.

3. 범위 검색이 빠름(B+tree 기준)

• b+tree 기반 인덱스는 리프 노드가 정렬된 연결 리스트 형태로 존재하기 때문에 where age Between 20 And 30 같은 범위 검색이 매우 빠름
• 한번 찾은 위치에서 순차적으로 읽어나가면 되기 때문이다.

4. 인덱스만으로 쿼리를 처리할 수도 있음(Covering Index)

• 일부 경우에는 테이블을 조회할 필요 없이 인덱스만으로도 결과를 반환할 수 있다.
• 예를들어, Select age From users Where age = 30; 쿼리는 age 칼럼에 인덱스가 있다면 테이블을 읽지않고 바로 처리 가능하다. 이를 Covering Index라고 한다

인덱스를 사용해야 하는 이유

인덱스가 걸려 있지 않으면

• 조건문 실행시 모든 행을 다 한번씩 찾아서 조건에 맞는 데이터를 뽑아서 출력해야함 (Full Scan = table scan)
• 시간 복잡도 : O(N)

인덱스가 걸려있다면

• 조건문 실행시 인덱스를 활용하여 조건에 맞는 데이터가 있는 위치를 빠르게 찾아 불필요한 행을 조회하지 않고 필요한 데이터만 가져옴

• 시간 복잡도 : O(logN) B-tree 구조일 경우

⇒ 조건을 만족하는 행을 빠르게 조회하기 위해 사용한다

⇒ 나아가 빠르게 정렬하거나 그룹핑 하기 위해서도 사용된다

B-tree 란?

각 노드가 두 개 이상의 자식 노드를 가질 수 있고, 모든 리프 노드가 같은 깊이를 가지는 특성을 지닌다. 주로 대용량 데이터를 처리하는 데 사용됩니다

B-tree는 데이터베이스나 파일 시스템에서 자주 사용되는 자료구조로, 균형잡힌 다중 경로 트리이다. 이 구조는 데이터를 효율적으로 검색하고 삽입/삭제할 수 있도록 설계되어 있다.

B-tree에서 중요한 점은 각 노드가 여러 자식 노드를 가질 수 있다는 점이다. 보통 이 트리는 키를 기준으로 데이터를 저장하는데, 각 노드는 여러 개의 키와 자식 노드를 포함한다. B-tree는 트리의 높이를 최소화하면서도 검색 속도를 최적화할 수 있기 때문에 대용량 데이터를 다루는 시스템에서 주로 사용된다.

이 구조의 핵심 특징은
첫째, 트리의 모든 리프 노드는 동일한 깊이를 가진다.
둘째, 각 노드의 키는 정렬되어 있으며, 이로 인해 이진 검색처럼 빠른 검색이 가능하다.
셋째, 노드의 크기는 사전 정의된 범위 내에서만 확장되거나 축소된다.

B-tree는 균형성을 유지하면서 삽입과 삭제가 이루어지기 때문에, 최악의 경우에도 O(log N)의 시간 복잡도를 보장한다. 이로 인해 대규모 데이터베이스에서 매우 효율적인 검색 및 업데이트 작업을 할 수 있게 된다.

B-tree 기반 인덱스 동작 방식

데이터베이스에서 인덱스는 검색 속도를 최적화하기 위해 사용되며, 특히 B-Tree 기반 인덱스는 균형을 유지하면서 빠르게 데이터를 찾을 수 있도록 설계된 구조다.

1. 인덱스 테이블의 구조

예를 들어, MEMBERS 테이블에 a, b, c 칼럼이 있다고 가정하자.
여기서 a 칼럼에 인덱스를 생성하면, B-Tree 인덱스 테이블이 다음과 같은 방식으로 구성된다.

a 값들을 정렬된 상태로 저장 (가장 작은 값부터 큰 값까지)
각 값에는 "포인터"가 포함됨 → 해당 값이 실제 테이블의 어느 행에 위치하는지를 가리킴
즉, "정렬된 데이터 + 실제 데이터의 위치 정보" 가 합쳐진 것이 인덱스 테이블이다.

---

2. B-Tree 인덱스를 이용한 검색 과정

예를 들어, 다음과 같은 검색을 실행한다고 가정하자.

SELECT * FROM MEMBERS WHERE a = 9;

이 경우, 데이터베이스는 B-Tree 인덱스에서 이진 탐색(Binary Search)을 수행하여 데이터를 찾는다.

1. 가운데 값(예: 5)을 선택

2. 찾고자 하는 값(9)과 비교

   • 9가 5보다 크므로 5 이하의 값들은 무시하고 오른쪽으로 탐색

3. 남은 범위에서 다시 가운데 값을 선택(예: 8)하고 비교

   • 9가 8보다 크므로 다시 오른쪽으로 이동

4. 반복하여 정확한 값을 찾음

5. 포인터를 이용해 실제 테이블에서 해당 행을 조회

그리고 같은 값이 존재할 경우(중복된 값), 연속된 인덱스를 따라 추가로 조회하여 해당하는 모든 행을 가져온다.

B+tree 란?

b+tree는 b-tree에서 검색 성능을 더 최적화한 구조로, 데이터베이스 인덱스에서 가장 많이 사용된다.
b+tree는 모든 데이터가 리프 노드에만 저장되며, 리프 노드끼리 링크드 리스트로 연결되어 있다. 이 덕분에 범위 검색과 순차 탐색에서 더 효율적이다.

B+tree 검색 과정

b-tree와 검색 과정은 동일한데 b+tree는 내부 노드에서 데이터를 찾을 수 없고 항상 리프 노드까지 가야한다.
내부 노드에는 데이터가 없고 리프노드로 갈수있는 키만 저장하기 때문이다.
하지만 내부 노드에서 값 비교는 가능하다.

b-tree와 차이점

1. 리프 노드에만 실제 데이터를 저장한다 -> 내부 노드는 검색을 위한 키만 존재한다.
2. 리프 노드가 서로(Linked List구조) -> 범위 검색 최적화 자료구조이다.
3. 탐색 방식은 b-tree와 동일하지만, 리프까지 가야 데이터를 찾을 수 있다.
   ※ MYSQL, PostgreSQL 등에서는 b+tree 구조를 따른다.

인덱스를 사용할때 주의할점

index(a)를 만들어놨다고 가정해보자 그때 where a=7 and b=95 라는 검색을하면

a조건을 찾는데는 빠르게 찾을수있지만

b조건을 찾는건 full scan이 일어난다

그래서 이 조건을 검색할땐 index(a,b)를 사용하는 복합 인덱스가 필요하다.

복합 인덱스는 a를 기준으로 정렬되고 그 다음 b 를 정렬한다

만약에 index(a,b)가 있을때 where a=2; 를 찾는다면 이럴땐 index(a,b)를 사용해도 된다.

복합 인덱스지만 a를 먼저 정렬했기 때문에 가능하다.

※ 예외로 조건이 or 로 연결되어 있으면 인덱스가 하나씩 따로 있어야한다.
-> mysql 버전에 따라 다르다... 5.7이하 에서는 인덱스 사용을 못하는 경우가 많고 8.0 이상에서는 OR에서도 다중 인덱스 사용이 가능해졌다..

검색시 사용한 인덱스 찾기

• EXPLAIN 키워드를 통해서 사용한 key를 보면 index 아이디가 나와있다.

• optimizer가 알아서 적절한 index를 선택하기 때문에 어떤 index를 사용한지 알아야 때 사용한다.

• 물론 인덱스는 골라서 사용할수도있음

• use는 권장 느낌이고 확실하게 사용하고싶으면 force를 사용한다.

• 하지만 force를 사용해도 optimizer가 index를 사용했을때 성능이 제대로 나오지 않을거 같으면 full scan을 선택한다.

• ignore index하면 제외도 가능하다

인덱스는 많이 만들수록 좋은거 아닌가?

1. 테이블에 새로운 데이터 insert, delete, update 가 발 생하면 모든 index에도 발생한다
   • 이렇게 때문에 오버헤드가 발생함
   • 오버 헤드 : 어떤 작업을 수행할때, 실제 필요한 적업외 추가적으로 발생하는 비용
2. 인덱스를 생성하면 추가적인 저장 공간을 차지함

Hash index

index는 무조건 b-tree 기반으로만 동작하는 것이 아니다. 다양한 방식으로 구현될 수 있는데 그중 hash index라는 방식도 존재한다
Hash index는 특정 조건에서 매우 빠른 성능을 보일 수 있지만, 몇 가지 특징과 제약사항이 존재한다.

특징

1. 빠른 검색 성능 (O(1))

Hash Index는 해시 테이블을 사용하여 데이터를 저장하고 검색합니다. 해시 함수가 데이터를 특정 버킷에 매핑하기 때문에, 일반적으로 O(1)의 시간 복잡도를 가집니다. 즉, 검색 속도가 매우 빠르다는 장점이 있습니다.

2. Rehashing에 대한 부담

데이터가 많이 추가되거나 삭제될 때, rehashing(해시 테이블의 크기를 다시 조정하는 과정)이 필요할 수 있습니다. 이 과정에서 성능 저하가 발생할 수 있습니다.

3. Equality 비교만 가능

Hash Index는 같은 값(equality comparison)을 비교하는 데에만 적합합니다. 즉, = 조건에서는 잘 동작하지만, 범위 조건(range comparison), 예를 들어 >나 <와 같은 연산에서는 사용할 수 없습니다. 그래서 범위 검색이 필요한 경우에는 B-Tree 인덱스가 더 유리합니다.

4. 멀티컬럼 인덱스의 제약

멀티컬럼 인덱스가 있을 경우, 전체 칼럼에 대한 조회만 가능합니다. 예를 들어 (a, b)와 같은 멀티컬럼 인덱스를 생성했다면, a와 b 컬럼을 모두 조회해야만 인덱스를 사용할 수 있습니다. 반면, B-Tree 인덱스는 단일 컬럼만으로도 검색이 가능합니다. 즉, (a, b) 인덱스를 만들었을 때, a 컬럼만을 사용하여 조회할 수 있는 B-Tree 인덱스와 달리 Hash Index는 두 컬럼 모두를 사용해야 효율적입니다.

Full scan이 더 좋은 경우

때로는 index를 사용하지 않고 테이블의 전체 데이터를 스캔하는 방법이 더 효율적일 수 있다. 이를 full scan이라고 한다. 다음과 같은 경우가 full scan이 더 좋은 경우이다.

1. 테이블 데이터가 적을 때
   테이블에 저장된 데이터가 적은 경우, full scan이 오히려 더 빠를수 있다. 인덱스를 사용하는데 드는 오버헤드보다 데이터를 직접 스캔하는 것이 효율적일 수 있다.

2. 조회 하려는 데이터가 데이블의 상당 부분을 차지할때
   이 경우 인덱스를 사용하더라도 성능 향상이 크지 않기 때문에 optimizer가 자동으로 full scan을 선택할 수 있다.

※ 정확히는 데이터의 20~30% 이상을 조회하면 인덱스를 사용하지 않고 Full scan을 선택할 가능성이 높다.

결론

이번 글에서는 index에 대해서 자세히 알아보았다. 이제는 어떤 상황에서 index를 사용해야 적절한지 알게되었다. 글을 늘려가면서 막연하게 사용하기 보다 적절한 상황에 공부한 내용들을 사용할 수 있을것 같다.