[Database] Clustered Index와 Non-Clustered Index

1. Index란?

---

혹시 테이블에 데이터를 저장할 때 특정 컬럼을 기준으로 정렬하여 저장하고싶다는 생각을 해보신적 있으신가요? 🤔

그런게 왜 필요하냐구요? 알고리즘을 공부해보신 분들은 아실겁니다.. 탐색의 전제는 정렬이라는 것을요 !

만약에 '이름'이라는 컬럼이 있고 제가 홍길동이라는 이름을 가진 데이터를 검색하고싶을 때, '이름'을 기준으로 정렬이 되어있다면 맨 뒷쪽의 'ㅎ'부터 찾아나가면 될 것입니다. Index는 바로 이런 특정 컬럼을 기준으로 정렬하여 데이터를 저장해놓고 싶을 때 사용합니다.

2. Clustered Index란?

---

아래와 같이 DB에 10개의 데이터를 저장한다해보겠습니다.

[그림 1] 입력 데이터

위와 같은 데이터를 SQL문을 통해 DB에 저장하게되면, 내부적으로 아래와 같은 Data Page 단위로 저장됩니다.

[그림 2] Data Page 단위로 데이터 저장

위와 같이 DB가 기본적인 방식으로 Data Page에 데이터를 저장하는 방식을 힙(Heap) 형태로의 저장이라고 합니다.

힙 형태로의 저장에서 이름이 '이상준'인 데이터를 조회하면 DB는 어떤 방식으로 데이터를 찾을까요? 🤔

알고리즘을 공부해보신 분들은 아시겠지만, 탐색의 전제조건은 정렬입니다. 그런데 위 Data Page들을 보면 이름으로 정렬되어있지 않습니다. 따라서, DB는 해당 데이터가 몇 번째 Data Page의 몇 번째 행에 위치해 있는지 알지 못하기 때문에 1번 Data Page의 1행부터 차례대로 검색해 나가는데, 이를 테이블 스캔(Table Scan)이라고 합니다.

 

검색의 성능을 향상시키기 위해 이름을 기준으로 정렬해보겠습니다. 다른 말로, '이름' 컬럼으로 Index를 생성해보겠습니다.

그럼 다음과 같이 Index Page가 생성됩니다.

[그림 3] '이름'을 기준으로 Index 생성

위와 같이 '이름'을 기준으로 인덱스를 생성하게되면 다음과 같은 과정을 거칩니다.

1. 기존의 Data Page의 데이터들이 '이름'을 기준으로 정렬되어 새로운 Data Page에 저장된다.
2. Index Page라는 별도의 Page가 생성되고, 각각의 Data Page 번호와 해당 Data Page의 첫 번째 데이터가 저장된다.
3. 기존의 힙 형태 구조를 가진 Data Page는 삭제된다.

이때, 각각의 Data Page를 리프 페이지(Leaf Page)라고 하고, 각 리프 페이지의 번호와 첫 번째 데이터를 가지고 있는 Index Page를 루트 페이지(Root Page)라고 부릅니다. 🧐

 

이제 다시 이름이 '이상준'인 데이터를 조회하면 다음과 같은 과정을 통해 데이터를 찾게 됩니다.

1. Index Page에서 3행의 '장은비'보다 작기 때문에 그 이전인 '박유선'을 첫 번째 데이터로 가지는 Data Page 5를 찾아간다.
2. Data Page 5에서 차례대로 읽어가며 이름이 '이상준'인 데이터를 찾는다.

위와 같은 검색 방법을 인덱스 스캔(Index Scan)이라고 하며, Index Page를 참고해 특정 리프 페이지만을 검색하기 때문에, 전체 Data Page를 검색하는 테이블 스캔(Table Scan)보다 검색 속도가 훨씬 빠릅니다.

3. Non-Clustered Index란?

---

Clustered Index는 특정 기준 컬럼(여기선 '이름')으로 Data Page 자체를 정렬하는 구조였습니다.

그런데 '이름'이 아니라 '휴대폰 번호'로 검색하면 어떻게 될까요? 🤔

'휴대폰 번호'로는 정렬이 되어있지 않기 때문에  리프 페이지를 다시 처음부터 끝까지 하나하나 검색해 나갈 것입니다.

'이름'을 기준으로 인덱스를 생성해 데이터를 정렬해서 저장해놓았는데 정작 검색조건은 다른 컬럼이니.. 인덱스화된 Data Page들을 처음부터 끝까지 하나하나 찾아보겠다라고 해서 이를 전체 인덱스 스캔(Full Index Scan)이라고 부릅니다.

 

위 Clustered Index는 정렬기준 컬럼으로 Data Page 자체를 새로 정렬해서 저장합니다. 그럼 여기서 다른 컬럼으로 새로 Clustered Index를 생성하면 다시 Data Page 자체를 새로 정렬해서 저장할겁니다.

 

눈치채셨나요? 여기서 Clustered Index의 큰 단점이 나옵니다.

Clustered Index는 하나의 컬럼을 기준으로 Data Page 자체를 정렬하기 때문에 테이블 당 하나밖에 생성하지 못한다는 것입니다.

이때 Non-Clustered Index로 문제를 해결할 수 있습니다. 다음은 '휴대폰 번호'로 Non-Clustered Index를 생성한 경우입니다.

[그림 1] '휴대폰 번호'를 기준으로 Non-Clustered Index를 생성했을 때

위 Clustered Index와의 차이점이 보이시나요? 🤔

Non-Clustered Index는 Data Page를 전혀 건드리지 않고, '휴대폰 번호'를 기준으로 정렬된 Index Page를 별도로 생성해서 저장합니다. 보시면 Index Page들간에 Root와 Leaf로 나뉘어져 있는 것을 볼 수 있는데, Clustered Index와 마찬가지로 Root Index Page는 각각의 Leaf Index Page들의 시작 주소를 가지고 있습니다. 그리고 Leaf Index Page를 보시면 Data Page 1:1 이런 식으로 되어 있는데, 이는 해당 데이터가 몇 번째 Data Page의 몇 번 행에 있는지를 가르킵니다. 즉, Index Page라는 것은 결국 주소만을 저장하고 있고, 데이터 자체는 Data Page에 저장한다는 것을 알 수 있습니다.

 

Clustered Index가 단일 포인터라면 Non-Clustered Index는 이중 포인터인 셈입니다. 😉

 

'휴대폰 번호' 컬럼으로 Non-Clustered Index를 생성하면 다음과 같은 과정을 거치게 됩니다.

1. Leaf Index Page를 생성하고, '휴대폰 번호'를 기준으로 정렬된 키와 해당 휴대폰번호의 Data Page에서의 위치 값을 저장합니다. 위치는 [파일번호 : Data Page 번호 : Row 번호]로 구성되는데, 이를 RID(Row Identifier)라고 부릅니다.
2. Root Index Page가 생성되고, 각각의 Leaf Index Page와 그 시작 주소를 저장합니다.

그럼 이제 '휴대폰 번호'가 '01064927878'인 데이터를 검색하면 어떻게 될까요?

[그림 2] '휴대폰 번호'가 ' 01064927878 '인 데이터를 검색했을 경우

검색했을 때의 과정은 다음과 같습니다.

1. Root Index Page에서 Leaf Index Page를 찾아간다.
   이를 인덱스 시크(Index Seek)라고 부릅니다.
2. Leaf Index Page에서 RID(Row Identifier)를 보고, 실제 데이터가 저장되어있는 Data Page를 찾아간다.
   이를 RID Lookup이라고 부릅니다.

4. Index 구조에서의 데이터 삽입

---

Clustered Index나 Non-Clustered Index인지에 상관없이 Index 구조는 검색의 성능을 향상시키지만, 삽입, 삭제에 대해선 성능이 현저히 떨어집니다. 아래와 같이 '이름'으로 정렬된 Clustered Index 구조가 있다고 해보겠습니다.

[그림 3] '이름'을 기준으로한 Clustered Index

이때, [고객번호: 00011, 이름: 도화지, 휴대폰번호: 01045458989] 인 데이터를 삽입하면 어떻게 될까요? 🤔

[그림 4] 데이터 삽입 과정의 모습

데이터 삽입시 행해지는 과정은 다음과 같습니다.

1. 삽입하고자하는 이름이 '도화지'인 데이터는 '구본지' 다음에 위치해야하지만 비어있지 않습니다.
   따라서, '문가람'을 새로운 Data Page로 이동시키고, '구본지' 다음에 '도화지'를 위치시킵니다.
2. 새로운 Data Page가 생겼기 때문에, Root Index Page에도 해당 Data Page에 대한 정보를 추가합니다.

 

즉, Index는 검색의 성능을 향상시키지만 너무 남발할 경우 삽입, 삭제에서 성능을 현저히 떨어뜨릴 수 있습니다. 😉