인덱스의 종류에 대해서 알아보자 !

0. 서론

인덱스의 개념에 대해서 궁금하신 분은 이전글 (DB 인덱스 개념 정리: 저장 구조, 생성 과정, 동작 원리) 를 참고해주세요 !

(1) 인덱스란 ? (개념, 구조, 남발하면 안되는 이유)

 

인덱스를 분류할 때, 크게

1. 구조 기반 인덱스
2. 저장 방식 기반 인덱스

로 나누어지는데요

 

각각의 분류에 속해있는 인덱스들에 대해서 지금부터 알아보도록 하겠습니다 ✌️

---

1. 구조 기반 인덱스

구조 기반 인덱스에는 정말 다양한 종류의 인덱스가 속해있는데요!

이번 포스팅에서는 대표적인 몇 개의 인덱스를 알아보도록 하겠습니다.

• B-tree Index
• B+Tree Index
• BitMap Index
• IOT Index

 

1-1. B-Tree Index

 

B-Tree는 가장 보편적으로 사용되는 인덱스 구조이며, 균형 탐색 트리(Balanced Search Tree) 입니다

균형 탐색 트리란 ?
트리의 높이가 균형을 유지하도록 자동으로 조정되는 이진탐색 트리를 의미합니다
그렇기 때문에 트리의 높이가 최소한으로 유지되고, 이를 통해 검색 / 삽입 / 삭제 연산이 O(log n) 의 시간복잡도를 가집니다

 

트리를 구성하는 노드는 루트 노드 / 브랜치 노드 / 리프 노드로 나뉘어지는데 각각의 특징은 다음과 같습니다 !

	위치	내용	설명
루트 노드	트리 최상단	키와 포인터	최소 2개의 자식 노드를 가진다 (단, 루트 노드 가 리프노드 일 경우는 예외)
브랜치 노드	중간 노드들	여러 개의 키와 자식 포인터	검색 시 키 값을 비교하면서 자식 노드로 이동
리프 노드	가장 하위 노드	실제 데이터 (레코드) 저장	오름차순으로 정렬

 

등호 및 부등호 연산을 효율적으로 처리할 수 있는 인덱스이며,

각 노드가 가질 수 있는 key 와 child 개수는 DBMS 설정 및 블록 크기에 다라 다릅니다

 

 

1-2. B+Tree Index

 

B+Tree는 이름에서 알 수 있듯이 B-Tree의 확장(개선)된 버전입니다! 🚀
B+Tree는 자식 노드가 2개 이상인 B-Tree를 개선한 인덱스 구조로,
많이 사용하는 DBMS 중 하나인 InnoDB (MySQL의 기본 스토리지 엔진)도 B+Tree Index를 사용하고 있습니다.

 

B-Tree 와 B+Tree 의 가장 큰 차이점은 데이터 저장 방식입니다 !

특징	B-Tree	B+Tree
브랜치 노드	키, 데이터 저장 가능	키만 저장
리프 노드	일부 데이터 저장 가능	모든 데이터 저장 (포인터 포함)
리프 노드 간 연결	X (범위 검색 비효율적)	Linked List 로 연결 (범위 검색 빠름)
검색 속도	다소 느림	일관된 검색 성능 (항상 리프 노드에서 데이터를 찾기 때문)

 

실제 데이터는 오직 리프 노드에만 저장되며, 모든 리프 노드가 Linked List 로 연결되어 있기 때문에 

범위 검색 성능이 B-Tree 보다 훨씬 빠릅니다 !!!!

 

리프 노드가 Linked List 로 연결되어 있다는게 왜 빠른건지 이해가 안 될 수 있는데요 🤔

B+Tree에서 50을 검색한다고 가정하면:

 

1️⃣ 브랜치 노드에서 50이 어디에 위치하는지 탐색 (브랜치 노드는 키만 저장)
2️⃣ 리프 노드까지 이동하여 50을 찾음 (모든 데이터는 리프 노드에 저장됨)
3️⃣ 만약 50보다 큰 값을 찾고 싶다면? → 리프 노드끼리 Linked List로 연결되어 있어 쉽게 이동 가능 ✅

 

만약 B-Tree 에서 50을 검색하고, 50보다 큰 값을 찾고자 한다면?

B-Tree 는 리프 노드끼리 연결되어 있지 않기 때문에 다시 브랜치 노드를 탐색해야 할 수도 있습니다

그렇기 때문에 범위 검색 시 불필요한 탐색이 발생하여 성능이 저하됩니다 🥺

 

 

1-3. Bitmap Index

Bitmap Index 는 중복 값이 많은 컬럼에서 최적의 성능을 제공하는 인덱스입니다

(예 : 성별, 국가 코드, 상태 값 등과 같이 값의 종류가 적고, 중복이 많은 경우)

 

컬럼 값을 비트맵(BitMap)으로 변환하여 저장하며, ROWID를 통해 해당 데이터 위치를 추적합니다

비트로 변환하여 저장하기 때문에 AND, OR 같은 논리 연산도 비트 연산으로 처리하여 빠른 검색이 가능합니다

 

하지만, INSERT / UPDATE / DELETE 시 비트맵을 재구성해야하기 때문에 성능 저하가 발생합니다.

 

 

1-4. IOT Index

IOT 의 풀 네이밍은 Index Organized Table 로 테이블 자체를 B-Tree 인덱스 구조로 저장하는 특수한 형태의 테이블입니다.

 

일반적인 인덱스는 ROWID 를 저장하여 테이블을 참조하지만, 

IOT 는 데이터 자체를 인덱스 리프 노드에 저장합니다 !!

 

테이블을 조회할 필요가 없기 때문에 검색 성능이 향상될 수 있지만, 

인덱스의 크기가 커질 수 있으며 업데이트가 빈번하면 성능이 저하됩니다

정적인 데이터나 읽기 위주 데이터 등에 적합합니다

---

2. 저장 방식 기반 인덱스

저장 방식 기반 인덱스는 구조 기반 인덱스와는 다르게 데이터가 디스크에 저장되는 방식에 따라 인덱스를 구성합니다 !

한마디로 설명하자면, 데이터의 물리적 구성에 따라 인덱스가 설계되는데요

 

저장 방식 기반 인덱스는 크게 두가지로 나뉩니다  !!

1. Clustered Index
2. Non-Clusted Index

 

2-1. Clustered Index

 

데이터 자체가 정렬된 인덱스의 순서대로 디스크에 저장되는 방식입니다 !!

 

예를 들어 책에서 "인덱스"  라는 키워드를 찾고자 할 때 Clustered Index 는 해당 키워드가 있는 페이지를 알고 있어서 해당 페이지를 바로 펼칠 수 있습니다. 

 

물리적으로 정렬되어 있기 때문에 검색 성능이 굉장히 뛰어납니다.

특히 범위 검색을 할 때 더욱 유리합니다.

 

데이터를 물리적으로 정렬된 형태로 저장힉 때문에 하나의 테이블에 하나의 클러스터드 인덱스만 존재가능합니다 !

그렇기 때문에 보통 PK 를 기준으로 클러스터드 인덱스가 자동 생성되는 경우가 많습니다.

 

 

 

2-2. Non-Clusted Index

 

Non-Clusted Index 는 데이터 자체가 정렬되어 저장되는 Clustered Index 와는 다르게

데이터가 정렬되지 않은 상태에서 별도의 인덱스 테이블을 두고 검색을 하는 방식 입니다

 

예를 들어 책에서 "인덱스" 라는 키워드를 찾고자 한다면 목차에서 해당 키워드의 책 페이지를 찾고, 페이지를 펼칠 수 있습니다 

 

데이터를 물리적으로 정렬해서 저장하지 않기 때문에 하나의 테이블에 여러 개의 논클러스터드 인덱스를 만들 수 있습니다

 

 

2-3. Clustered Index vs Non-Clusted Index

	Clustered Index	Non-Clustered Index
데이터 정렬 방식	디스크에 정렬 저장	정렬되지 않음
검색 속도	빠름 (데이터가 정렬되어 있기 때문)	다소 느림 (목차를 통해서 찾아야함)
삽입 / 삭제 속도	느림 (모든 데이터를 재정렬)	빠름 (목차에 추가만)
테이블 당 개수	1개만 가능	n개 가능
활용	자주 검색되는 컬럼 이나 PK	자주 필터링 되는 컬럼