[인덱스 채우기] 인덱스란?, B-Tree(+B+Tree), 클러스터 인덱스

✅ 인덱스를 머리에 채우기

인덱스가 당연히 있어야 하고 당연히 좋다고 생각하기 쉬운데...인덱스가 없더라도 데이터베이스가 작동하는 데에는 문제가 없다. 오히려 인덱스를 관리하는 데 비용이 증가할 수 있고, 성능도 저하될 수 있다. 하지만 데이터베이스의 크기가 커지면 인덱스의 필요성이 커진다. 인덱스는 그냥 있는 것이 아니라 다양한 인덱스 구조와 활용 방법이 있고 비용과 성능 측면을 고려하여 도입해야 한다. 그래서 인덱스를 머리에 좀 채워보려고 한다.

 

• 인덱스는 데이터의 읽기(SELECT) 속도를 빠르게 만들어주는 역할을 한다.
• 다만, 그 대가로 데이터의 쓰기 작업(INSERT, UPDATE, DELETE) 성능에 영향을 준다. 변경 작업이 자주 일어나거나, 인덱스가 적절하지 않으면 paging이 빈번해져 성능이 저하된다.
• 인덱스를 저장하면 당연히 이를 저장할 공간이 필요하다. (DB의 10%정도 되는 추가 공간)
• 인덱스는 테이블 데이터를 기반으로 만들어지지만, 물리적으로는 테이블과 다른 저장 공간에 별도로 저장된다. 테이블은 데이터를 저장하고, 인덱스는 테이블의 특정 컬럼 값과 해당 행의 위치(RowID)를 매핑하는 별도의 데이터 구조를 관리한다.
• 클러스터 테이블(cluster table)에서도 인덱스를 사용할 수 있지만, 인덱스 자체는 테이블/클러스터와 독립된 공간에 저장된다.

 

💡 클러스터 테이블은 주로 Oracle DB에서 사용하는 용어로, 여러 테이블을 하나의 클러스터(하나의 저장 단위, 블록)에 묶어서 저장하는 방식을 말한다. 특정 공통 컬럼(클러스터 키)값을 기준으로, 서로 다른 테이블의 행들을 같은 데이터 블록에 저장한다. 조인을 자주 수행하는 테이블의 I/O 성능을 개선해준다. 

예를 들어,
STUDENT(student_id, name) GRADE(student_id, subject, score)라는 두 테이블이 있다고 할 때, 두 테이블을 student_id로 클러스터링하면, 같은 student_id를 가진 데이터가 같은 블록에 저장된다. 결과적으로 조인 시에 성능이 올라가는 것이다.

 

 

 

 

 

 

---

 

 

 

 

 

클러스터 인덱스 (Clustered Index, Primary Index)

인덱스의 타입 종류에는 클러스터 인덱스(Primary Index)와 보조인덱스(Secondary Index)가 있다. 

 

클러스터 인덱스는 특정 기준에 따라 데이터를 정렬하는 인덱스이다.

예를 들어, 영어 사전처럼 데이터가 순서대로 정렬된 형태를 생각하면 된다.

 

• 클러스터 인덱스를 생성하면 데이터 페이지 전체가 인덱스 기준에 맞게 재정렬된다. 따라서 이미 대용량의 데이터가 입력된 상태라면 생성 시 상당한 시스템 부하가 발생할 수 있다.
• 한 테이블에는 오직 하나의 클러스터 인덱스만 생성할 수 있다.
• 일반 인덱스는 인덱스 자체에 별도의 배열 정보를 저장할 공간이 필요하지만, 클러스터 인덱스는 추가 공간을 적게 사용하면서 테이블 자체의 공간을 활용한다. 
• 이때 인덱스의 리프 페이지는 곧 데이터 페이지이므로, 인덱스 안에 데이터가 포함되어있다고 볼 수 있다. 
• 보조인덱스보다 검색 속도가 더 빠르지만, 입력/수정/삭제가 더 느리다. 
• MySQL에서는 Primary Key가 존재한다면 Primary Key를 클러스터 인덱스로 사용한다. Primary Key가 없다면 Unique + Not Null 컬럼을, 그것마저도 없으면 보이지 않는 컬럼을 임의로 만들어 클러스터 인덱스를 지정한다. 

 

 

 

 

---

B-Tree 인덱스 (Balanced Tree Index)

인덱스의 알고리즘 종류는 대표적으로 B-Tree 인덱스와 Hash 인덱스가 있고, 최근에는 Factal-Tree 인덱스 알고리즘도 도입되었다.

 

B-Tree인덱스는 가장 보편적으로 사용되는 인덱스 방식으로, MySQL에서도 사용된다.

 

• 인덱스가 항상 정렬된 상태를 유지하도록 한다.
• 각 트리의 레벨이 균형(Balance)을 이루기 때문에, 검색할 때 대부분 비슷한 시간(O(logN))안에 결과를 얻을 수 있다.
• B-Tree 인덱스는 컬럼 값을 변경하지 않고 원래의 값을 이용해 인덱싱한다.
• 루트 노드 → 브랜치 노드 → 리프 노드의 구조로 이루어진다.

💡 브랜치 노드(Branch Node)
루트노드(최상위 노드)도 아니고 리프노드(가장 하위의 노드)도 아닌 노드를 브랜치 노드라고 한다. 브랜치노드는 다음 노드를 찾아가는 길찾기 역할을 한다.

 

장점	단점
어떤 데이터를 조회하더라도 검색 경로와 비용이 일정하다. BETEWEEN, >=, <=, >, < 등 범위 조건 검색에서 성능 향상을 제공한다.	데이터를 조회할 때마다 항상 루트노드부터 리프노드까지 내려가야 한다. 따라서 작은 테이블에서 단순 조회 시 오히려 성능이 느릴 수 있다.

 

 

B+Tree

그러면 B+Tree라는 것도 있던데 이건 무엇일까? B+Tree는 B-Tree의 확장개념으로, B-Tree에서 검색 성능을 개선했다. MySQL의 InnoBD 같은 경우, 인덱스를 관리할 때 B+Tree를 사용한다.

• B+Tree는 내부 노드(루트, 브랜치 노드)는 데이터 주소만 저장하고, 실제 데이터는 리프 노드에만 저장한다. 
• 모든 리프 노드가 연결 리스트처럼 연결되어있어, 리프 노드간에도 순차 검색이 가능하다.

 

B-Tree vs B+Tree

예를 들어 A부터 B까지의 범위를 검색하는 상황을 가정해보자.

 

B-Tree의 case

1. 루트 노드부터 A 값을 찾기 위해 탐색

2. 루트 노드부터 B 값을 찾기 위해 또다시 탐색
→ 즉, 루트부터 리프까지 선형 탐색을 2번 해야한다.

 

B+Tree의 case

1. 루트 노드부터 A 값을 찾아 A가 위치한 리프 노드에 도달

2. 리프 노드끼리 연결된 포인터를(=연결성을 추가) 통해 B 값이 나올 때까지 오른쪽으로 순차 탐색
→ 루트부터 리프까지 탐색하는 작업은 1번만 수행하고, 나머지는 리프 노드 간 연결을 통해 빠르게 탐색할 수 있다.

 

 

 

 

 

 

하지만 B+Tree라고 무조건 좋은 것은 아니다.

• 메모리 효율 측면에서는 B+Tree가 좋다. 왜냐하면 B-Tree는 각 노드에 데이터도 저장하지만, B+Tree는 리프 노드에만 데이터가 저장되어있어 내부적으로는 더 작고 단순하다.
• 반면에 삽입/삭제 효율 측면에서는 B+Tree가 더 떨어질 수 있다. 왜냐하면 B+Tree는 '연결'을 나타내는 데이터가 추가적으로 관리되어야 하기 때문이다.