🔖 인덱스

🏗️ B-트리(B-Tree)

인덱스는 대개 B-트리라는 자료 구조로 이루어져 있습니다. 트리 구조는 최상단의 루트 노드(Root Node), 가장 끝단의 리프 노드(Leaf Node), 그리고 그 사이를 연결하는 브랜치 노드(Branch Node)로 나뉩니다.

• 탐색 효율성 예시: 만약 데이터 'E'를 찾는다고 가정해 봅시다. 인덱스가 없다면 A, B, C, D, E 순서대로 전체 테이블을 훑어야 하므로 5번의 탐색이 필요합니다. 하지만 B-트리 구조를 활용하면 루트에서 경로를 찾아 단 두 번 만에 리프 노드의 'E'에 도달할 수 있습니다.

 

구체적인 작동 원리 (Key: 57 검색 시): 키값 57을 찾는다고 가정할 때, 탐색은 항상 루트 노드에서 시작하여 브랜치 노드를 거쳐 리프 노드로 내려갑니다.

1. 루트 노드: 저장된 키가 39, 83이라면, 57은 39보다 크고 83보다 작으므로 그 사이 경로로 내려갑니다.
2. 브랜치 노드: 아래 노드에 46, 53, 57 등이 정렬되어 있습니다.
3. 리프 노드: 최종적으로 57이 있는 리프 노드에 도달하여, 해당 키가 가리키는 데이터 포인터를 통해 실제 데이터 값을 반환합니다.

🚀 인덱스가 효율적인 이유와 대수확장성

인덱스가 효율적인 이유는 균형 잡힌 트리 구조를 통해 트리 깊이의 대수확장성(Logarithmic Scalability)을 가지기 때문입니다.

대수확장성이란 데이터의 양이 늘어나도 트리의 깊이(탐색 단계)는 그에 비해 매우 느리게 증가하는 성질을 말합니다. 기본적으로 인덱스 깊이가 1단계 증가할 때마다 저장 가능한 최대 인덱스 항목 수는 4배(또는 그 이상)씩 기하급수적으로 늘어납니다.

트리 깊이	인덱스 항목의 수
3	64
4	256
5	1,024
6	4,096
7	16,384
8	65,536
9	262,144
10	1,048,576

위 표처럼 트리 깊이가 10단계만 되어도 약 100만 개의 레코드를 커버할 수 있습니다. 실제 상용 DB의 인덱스는 이보다 훨씬 효율적으로 설계되어 있어 수천만 건의 데이터도 빠르게 검색할 수 있습니다.

---

🛠️ 인덱스 만드는 방법

🐬 MySQL

MySQL의 인덱스는 크게 클러스터형 인덱스(Clustered Index)와 세컨더리 인덱스(Secondary Index)로 나뉩니다.

• 클러스터형 인덱스:
  • 테이블당 단 하나만 존재할 수 있습니다. (책의 페이지 번호와 유사)
  • Primary Key 옵션으로 기본키를 지정하거나, Unique Not Null 옵션을 주면 자동으로 생성됩니다.
  • 데이터 자체가 인덱스 순서대로 정렬되어 저장되므로 검색 속도가 가장 빠릅니다.
• 세컨더리 인덱스 (보조 인덱스):
  • CREATE INDEX ... 명령어로 생성하며, 여러 개 만들 수 있습니다. (책 뒤의 '찾아보기'와 유사)
  • 단일 필드뿐만 아니라 age, name, email 등 여러 필드를 묶어 쿼리할 때 유용합니다.
  • 하나의 인덱스만 필요하다면 클러스터형 인덱스를 우선적으로 고려하는 것이 성능상 유리합니다.

🍃 MongoDB

• 도큐먼트 생성 시 자동으로 생성되는 ObjectID가 기본키(_id) 역할을 하며 인덱스로 설정됩니다.
• 사용자가 필요에 따라 세컨더리 키를 추가하거나, 기본키와 세컨더리 키를 조합한 복합 인덱스(Compound Index)를 설정할 수 있습니다.

---

⚙️ 인덱스 최적화 기법

💸 인덱스는 비용이다

인덱스는 공짜가 아닙니다. 인덱스를 사용하면 '인덱스 리스트 탐색 → 실제 데이터(컬렉션) 탐색'이라는 두 번의 과정을 거치므로 읽기 비용이 발생합니다.

더 중요한 것은 쓰기 비용입니다. 데이터가 수정, 삽입, 삭제될 때마다 인덱스(B-트리)도 함께 수정되어야 합니다. 트리의 균형(Balance)을 맞추고 데이터를 분산시키는 과정에서 추가적인 연산 비용이 듭니다. 따라서 사용하지 않는 불필요한 인덱스는 제거해야 하며, 읽기보다 쓰기가 빈번한 시스템에서는 인덱스 설정을 신중히 해야 합니다.

🧪 항상 테스팅하라

최적화의 정답은 서비스의 데이터 특성에 따라 달라집니다. 객체의 깊이, 테이블의 크기, 데이터 분포도 등이 다르기 때문입니다. 반드시 explain() 함수를 사용하여 쿼리 실행 계획을 확인하고, 인덱스 적용 전후의 성능을 비교 테스팅해야 합니다.

//MySQL 테스팅
EXPLAIN
SELECT*FROM t1
JOIN t2 ON t1.c1=t2.cl

🔢 복합 인덱스는 같음, 정렬, 다중 값, 카디널리티 순이다

여러 필드로 구성된 복합 인덱스를 만들 때는 필드의 순서가 성능을 좌우합니다. 일반적으로 다음 우선순위를 따릅니다.

1. 같음 (Equality): ==이나 equal 조건으로 정확히 일치하는 값을 찾는 필드를 가장 먼저 둡니다.
2. 정렬 (Sort): 정렬(ORDER BY)에 사용되는 필드를 그 뒤에 둡니다.
3. 다중 값 (Range): >, < 등 범위를 조회하거나 많은 값을 출력해야 하는 필드는 나중에 배치합니다.
4. 카디널리티 (Cardinality):
   • 카디널리티란? 데이터 값의 유니크한 정도를 뜻합니다. (예: 주민번호는 높음, 성별은 낮음)
   • 카디널리티가 높은 필드(중복이 적은 필드)를 우선적으로 인덱싱해야 검색 범위를 효과적으로 좁힐 수 있습니다.
   • 예: age와 email 중에는 유니크한 email을 먼저 인덱스로 잡는 것이 유리합니다.