[DB] 📚 데이터베이스 인덱싱 🗂️ 구조 with MySQL

본 포스팅은 학교 수업에서 진행하는 이론,실습에 대해 정리하는 포스팅 입니다. 공부용으로 작성하는 포스팅으로 오류가 있을 수 있습니다.

 

데이터베이스에서 인덱스는 성능 최적화를 위한 핵심 도구로서 대규모 데이터 처리 속도를 획기적으로 향상시킬 수 있다.

이번 글에서는 인덱스의 개념, 작동 원리, 장단점, 사용시 유의사항 등을 다뤄본다. 

 

 

데이터베이스 인덱스란

인덱스는 책의 색인처럼, 데이터베이스 테이블에서 특정 데이터를 빠르게 찾을 수 있도록 설계된 자료 구조이다. 데이터 검색 시 전체 테이블을 스캔하지 않고, 인덱스를 통해 원하는 데이터에 빠르게 접근할 수 있다.

 

출처: 코딩애플 유튜브

데이터베이스에서 원하는 데이터를 조회할 때, 예시와 같이 쿼리를 짜고 접근하게 되면, 데이터베이스는 age 컬럼의 모든 값을 뒤지면서 조건에 맞는 값을 찾게 된다. 

만약 데이터가 100만개 존재하면, 100만개 데이터를 뒤져야한다.

 

하지만 이러한 컬럼이 미리 정렬이 되어 있다면? 정렬된 데이터 집합에서 특정 값을 빠르게 찾는 것이 가능해진다. 조회에 자주 쓰이는 특정 컬럼에 대해서 미리 정렬을 해두고 정렬한 데이터를 따로 저장해뒀다가, 해당 값을 조회해야 하는 경우 정렬된 저장본을 가져와 탐색 범위를 효율적으로 줄여가며 원하는 값을 찾아내는 것이 가능하다.

예를들어 1부터 100까지 순서대로 나열된 경우, 원하는 값이 76라면, 찾고자 하는 값과 탐색 중인 중간값을 비교하여, 나열된 데이터를 50부터 100까지 자르고, 50부터 100까지의 정보를 다시 75부터 100까지 잘라내어 탐색을 시작하면 원하는 값을 하나하나 데이터를 비교하는 것보다 훨씬 빠르게 구현할 수 있다.

이 정렬된 저장본을 인덱스 라고한다.

 

출처: 코딩애플 유튜브

이렇게 된 경우 문제점으로는, 인덱스를 사본으로 저장해둬야 하기 때문에, 저장공간을 더 차지하게 된다는 것

그리고 테이블에 새로운 데이터가 추가되거나 수정 혹은 삭제를 하게 되면 인덱스에도 반영을 해줘야하기 때문에 처리량이 늘어나 성능 하락이 될 수도 있다. 

그리고 Primary key로 지정된 데이터는 이미 정렬이 되어있는 상태이기 때문에 index생성이 따로 필요가 없다. -> clustered index

인덱스 구조

인덱스의 용도와 대략적인 작동방식을 다루었으니, 이제 인덱스가 어떤 구조로 만들어지는지 살펴보자

컴퓨터 내에서 데이터 자료를 정렬하여 사용하고 싶다 하면 다양한 자료구조를 채택할 수 있다. 자주 쓰이는 자료구조로 Array 또는 Linked List등이 있을것이다. 하지만, 실제 데이터베이스는 인덱스를 비선형 자료구조인 트리 구조로 저장한다. 

출처 : 코딩애플 유튜브

데이터를 계층적으로 구현하여 시간 복잡도를 O(logn)까지 줄이는 것이 가능하다. 이는 데이터가 많아질 수록 성능 차이가 매우 커짐을 알 수 있다. 

출처 : 코딩애플 유튜브

앞서 예제에서 다뤘던, 데이터를 반씩 나눠가며 찾는 방법을 이진 탐색(Binary Search)이라고 하고, 이러한 방식을 적용하여 정렬 시킨 트리를 Binary Search트리라고한다. 

여기서 노드마다 데이터를 하나가 아니라 2~3개씩 넣어주면 좀 더 성능을 개선시킬 수 있다. 이를 2-3Tree 라고한다. (혹은 차수가 3인 B-트리)

이렇게 구현하면 반씩 자르는게 아니라 1/3, 2/3씩 과감하게 자르면서 더 빠르게 데이터를 찾아나갈 수 있다.

여기서 좀 더 개선시킨 구조가 B+ tree인데, 트리의 맨 밑에서만 데이터를 저장하고, 그 위의 부모 노드들은 가이드라인만 제공을 하는 방식이다.  밑에 있는 데이터 끼리는 리스트로 연결되어 화살표로 이어져있다.

출처 : 코딩애플 유튜브

이렇게 되면 범위 검색이 매우 쉬워진다는 장점이 있다. 위 예시에서 4~8까지 범위에 해당하는 값을 찾고자 한다면, B-tree의 경우 분할된 경로를 따라 일일히 따라가면서 데이터를 서치해야한다.  (4->6->5->6->7->6->8) 

하지만 B+트리로 저장된 경우 그냥 4부터 찾은다음 8까지 쭈욱 이동하면 된다. 이처럼 범위검색이 매우 쉬워지고 서칭이 매우 빨라지게 되어 데이터베이스 성능을 향상시킬 수 있다. 데이터베이스 종류마다 차이는 있지만 대부분 이러한 구조로 데이터베이스의 인덱스 기능을 구현해두었다. 

 

트리 및 B+트리의 좀 더 자세한 구조는 아래 포스팅에서 다룬다.

 

Hash Function

위에서 다루었던 트리 구조가 대부분 사용되지만 간혹 HASH 구조를 함께 적용하는 데이터베이스가 존재한다.

Hash 구조도 마찬가지로 인덱스를 구현하거나 데이터의 빠른 검색을 가능하게 하는 핵심적인 요소 중 하나이다. 기존 B+ 트리 같은 구조와는 다른 방식으로 데이터를 저장하고 관리하여 빠른 데이터 접근을 제공한다. 이론상 O(1) 가능

 

Hash Function 은 키(key)를 정수(Integer)로 매핑(mapping)하여 데이터를 빠르게 저장하거나 검색하는데 사용된다.

 

Hash Table의 구성 요소는 다음과 같다.

 

1. Hash Function (h):
   • 키 값을 일정 범위 [0, N-1]의 정수로 변환
   • 예: h(x) = x mod N (정수 키에 대한 해시 함수).
   • 여기서 h(x)는 해시 값이라 불림
2. Array of Size N:
   • 해시 값을 기반으로 데이터를 저장하는 배열
   • 각 배열의 인덱스는 해시 함수의 출력값에 해당
3. 저장 목표:
   • (k, o) 데이터를 인덱스 i = h(k)에 저장하여 효율적인 검색 및 저장을 구현

• 예제:
  • SSN(주민등록번호)와 이름으로 구성된 데이터를 저장.
  • SSN은 9자리의 양수로 가정.
  • 해시 테이블 크기: N = 10,000.
  • 해시 함수: h(x) = x의 마지막 네 자리 라고할때

• 구현:
  • 예를 들어, SSN이 200-751-9998이라면, 해시 값 h(9998)을 통해 9998번 인덱스에 데이터를 저장.

 

이상적인 해시 함수

• 쉽고 빠르게 계산되며, 충돌이 거의 없는 해시 함수를 이상적인 해시 함수라 정의한다.
• 해시 함수는 두 단계의 함수 조합으로 구현된다.
  • Hash Code Map (h₁): 키(key)를 정수(integer)로 변환.
  • Compression Map (h₂): 정수를 해시 테이블의 인덱스 범위(0 ~ N-1)로 변환.
  • h(x) = h₂(h₁(x))

해시함수의 목적은 데이터를 무작위적으로 분산 시켜 충돌을 최소화하고 검색 효율을 극대화 시키는것

이상적인 조건을 만족하면 매우 빠른 성능을 보여주지만, exact match만 해당되고, range query는 불가능하다.

그래서 exact match에만 HASH를 사용하고, range 검색에는 BTREE를 사용하는 방식으로 두가지 구조를 모두 채택하는 경우가 있다

 

1. •  

Collision Handling (충돌 처리)

1. Chaining:
   • 각 셀에 연결 리스트를 두어 충돌 시 데이터를 저장.
   • 구현이 단순하지만, 추가 메모리가 필요.
2. Open Addressing:
   • 충돌 발생 시 테이블 내 다른 빈 셀을 찾아 데이터를 저장.
   • 충돌을 해결하기 위한 효율적인 공간 활용.

 

 

MySQL에서 Create Index

좌측의 코드는 Create Index를 사용하는 구문을 보여준다.

UNIQUE는 중복을 하용하지 않는 인덱스, FULLTEXT는 텍스트 검생용 인덱스, SPATIAL은 공간(지리 정보) 데이터를 위한 인덱스이다. [index_type]에는 BTREE 혹은 HASH를 지정해준다. 

추가 옵션으로 KEY_BLOCK_SIZE는 키 블록 크기를 지정하는 옵션, VISBLE 또는 INVISBLE은 인덱스를 쿼리에서 보이게 하는 설정과 숨기는 설정이다.

 

[algorithm_option] 은 인덱스 생성 방식을 지정하며 DEFAULT, INPLACE, COPY중 선택이 가능하다

[lock_option]은 인덱스를 생성하거나 변경하는 동안 테이블의 잠금(lock)방식을 설정한다.

 

우측에서는 예시를 보여준다.

• 기본 인덱스 생성 : CREATE INDEX idx1 ON t1 (col1 + col2); 
• 복합 인덱스 생성: CREATE INDEX idx2 ON t1 ((col1 + col2), (col1 - col2), col1);
• ALTER TABLE로 인덱스 추가: ALTER TABLE t1 ADD INDEX ((col1 * 40) DESC);
• 특정 엔진에서 인덱스 타입 지정하여 생성
  • CREATE TABLE lookup (id INT) ENGINE = MEMORY;
    CREATE INDEX id_index ON lookup (id) USING BTREE;

하단의 표에서는 스토리지 엔진이 지원하는 인덱스 타입을 설명한다.

1. InnoDB, MyISAM: BTREE 인덱스만 지원
2. MEMORY/HEAP, NDB: HASH와 BTREE 모두 지원(exact는 hash, range는 btree)

예시를 보면, 실제로 생성된 t1 테이블에 대해, DESC, EXLAIN을 통해 테이블 정보와 실행 계획을 확인한다. 

possible_keys와 key값이 null로 나타난다. 인덱스값이 없이 모든 데이터를 조회하고 있는 상태임을 알 수 있다.(rows=3으로 보아 데이터 3개)

 

create index로 인덱스 index_t1을 생성해주고 나서 desc t1;을 하면 key열에 MUL(Multiple Occurrences)이 추가되고, 해당 열에 인덱스가 적용되었음을 확인할 수 있다.

explain 결과에서는 where절 없이 쌩으로 select * from t1을 하면 다른게 없지만

where절을 사용해서 a값을 조건으로 조회하는 경우, 인덱스를 활용한 검색이 이루어지고 있음을 확인할 수 있다.

type은 ref가 되었고 possible_keys에 인덱스 이름 index_t1이 표시되며, key값도 index_t1으로 설정된다. rows필드 값도 3에서 1로 감소한다. 불필요한 데이터의 접근이 줄어들어 성능이 향상되었음을 알 수 있다.

또한, 인덱스를 설정한다 하더라도 모든 쿼리의 성능이 좋아지는 것이 아니라 조건에 맞는 인덱스만 쿼리 성능을 향상 시킨다는 것을 알 수 있다.

 

다음 내용에서 인덱스의 효율성에 대해 다루겠지만, 테이블에 인덱스가 많다고 무조건 좋은 것은 아니기에, 필요한 쿼리에 맞게 신중한 인덱스를 설정할 필요가 있다. 

 

EXPLAIN : MySQL에서 쿼리 실행계획을 확인하는데 사용되는 도구로, 쿼리가 실행될 때 데이터베이스가 어떤 방식으로 데이터를 검색하는지에 대한 정보를 제공한다. 이를 통해 최적화와 성능 개선의 단서를 얻을 수 있다.

DESC: 테이블 구조를 확이하는데 쓰이며, 테이블에 어떤 열이 있는지, 인덱스가 설정되었는지 등을 확인할 수 있다. 테이블의 스키마를 이해하는데 사용된다.

 

 

정리하자면 인덱스 타입에 따라, exact, range 쿼리는 아래와 같은 성능을 보인다.

• USING BTREE(B+ Tree) : range query ->  O(log n)
• USIGN HASH(extendible hash) : exact match query  -> O(n)~O(1)

인덱스 가이드라인

정리한대로, 인덱스는 데이터베이스 성능 최적화의 핵심 도구이다. 하지만 모든 경우에 인덱스를 사용하는 것이 효율적인 것은 아니다.

아래는 인덱스 설계와 사용 시 항목별 참고할 가이드라인이다. 

 

1️⃣ 키와 인덱스

• Primary Key: 기본적으로 인덱스가 자동 생성된다. (테이블에서 유일성을 보장하는 Column)
• Foreign Key: 관계형 데이터베이스에서 테이블 간 관계를 정의. 외래 키에 인덱스를 추가하면 조인 성능이 향상될 수 있음
• Alternate Key: Priamry key 외에 추가적으로 유일성을 보장해야 하는 경우 사용

위와 같은 key들은 결정자로서, 다른 컬럼들은 이러한 key에 종속적이기 때문에, key에 우선적으로 인덱스를 적용하는 것이 좋다.

 

 

2️⃣ 인덱스 효율성

인덱스로 어떤 컬럼을 선정할 지 고민될 때, 효율성을 따질 수 있는 지표가 있다.

 

• Selectivity:
  • 전체 레코드 중에서 조건절에 의해 선택되는 레코드 비율
  • 선택도 = 1 / NDV (where = 조건) *NDV (Number of Distinct Value) = 유일하게 구별되는 컬럼 값 종류의 개수
  • 선택도가 낮을 수록 인덱스 후보가 되기 좋다 (일반적으로 0~4%의 선택성을 가진 인덱스가 효율적.)

• Cardinality:
  • 전체 레코드 중에서 조건절에 의해 선택되는 레코드 개수 (실제 predicate에 의해서 추출되는 row 수를 의미)
  • 컬럼 값의 고유도. 값이 다양할수록 인덱스의 효율성이 높아짐.
  • 선택도에 총 레코드 수를 곱해서 구한다.

3️⃣ 동적 테이블과 인덱스

Dynamic 테이블에는 인덱스가 불필요

-> 데이터의 삽입(insert) 및 삭제(delete)가 빈번한 테이블에서는 유지 비용이 높아져 비효율적.

 

4️⃣ 인덱스 개수

테이블당 3~4개 이하로 제한하는 것이 좋다. 너무 많은 인덱스는 데이터 변경 시 성능을 저하시킬 수 있다.(인덱스에도 반영을 해줘야 하므로)

 

 

5️⃣ 데이터 타입과 인덱스

VARCHAR 대신 정수(Integer)나 CHAR 같이 고정길이 타입을 사용하는 것이 효율적이다. 

VARCHAR는 길이가 가변적이어서 비교와 저장 시 추가 비용이 발생한다.

 

6️⃣ 테이블 크기와 인덱스

작은 테이블은 인덱스가 필요하지 않을 수 있다. 테이블 크기가 작으면 풀 테이블 스캔이 더 빠를 수 있기 때문이다. 처음 예시에서 인덱스를 도입하고자 하는 경우를 100만개의 데이터가 있는 경우로 설정한 것 처럼, 테이블에 투플이 많아 전체 스캔이 부담스러운 상황에서 인덱스를 적용하는 것이 좋다.

 

 7️⃣ 인덱스 도입 시점

큰 테이블에 인덱스를 적용해야 하는 경우, 인덱스는 처음부터 설정하면 안된다. 인덱스를 설정하고 데이터를 넣게 되면 시간이 오래걸리게 된다.(데이터베이스에 데이터를 넣을 때마다, 인덱스에도 같이 데이터를 넣어줘야 하기 때문에) 

가능하면 필요한 데이터들 Insert를 먼저 하고, 인덱스를 걸어주는 것이 좋다.

 

8️⃣ 정렬 작업과 인덱스

ORDER BY와 GROUP BY 같은 작업이 빈번한 경우에도 인덱스를 활용하면 성능을 향상시킬 수 있다.

 

9️⃣ WEHERE 조건과 인덱스

인덱스는 아래 조건에서 특히 효과적이다.

• WHERE id = 특정값 을 하는 경우
• LIKE 조건 ( ex: LIKE 'abc%')
• 범위 조건 (ex: id BETWEEN 2 AND 8).

반대로 전체 검색을 하는 경우(ex: WHERE created_at IS NOT NULL)에는 인덱스가 활용될 일이 많지 않아서 비효율적이다.