DB Index (RDBMS)

 
우테코의 테코톡에서 잘 설명해줘서 두고 두고 보려고 기록하는 글.
 

Index와 DB Index

---

인덱스는, 쉽게 찾아볼 수 있도록 일정한 순서에 따라 놓은 목록을 말한다. 현재 데이터가 아무 기준 없이 저장된 상태라면 뒤죽박죽이라서, 특정 키워드를 찾으려 하면 모든 데이터를 순차적으로 탐색해야 한다. 그러나 데이터가 특정 기준으로 정렬되어 있다면 검색을 빠르게 할 수 있다.
 
DB 인덱스는, 데이터베이스 테이블에 대한 검색 성능을 향상시키는 자료구조로, WHERE절 등을 통해서 활용된다.
이메일을 인덱스로 정한다면, 이메일 컬럼에 대한 값을 복사해서 이걸 abc 순으로 정렬한 데이터가 생긴다. 여기서"SELECT * FROM member WHERE email = 'ehl3288@naver.com'을 실행하면 email로 정렬된 데이터(인덱스 적용된 대상)를 검색하고, "SELECT *FROM member" 라고 where 절을 빼고 실행하면 인덱스가 사용되지 않는다.
 
이외에도 아래와 같은 특징을 가진다.

• 인덱스는 항상 최신의 정렬상태를 유지한다.
• 인덱스도 하나의 데이터베이스 객체다.
• 데이터베이스 크기의 약 10% 정도의 저장공간이 필요하다.

 

Index 알고리즘

---

페이지 : 데이터가 저장되는 단위로, MySQL 기준으로 16Kbyte 정도다.
 

Full Table Scan

처음부터 순차적으로 탐색하는 것으로, 접근 비용이 적다.
아래 그림에서는 PPP를 찾는데 3개 페이지에서 12번의 검색이 있었다.

Full Table Scan

Full Scan이 이뤄지는 경우는 아래와 같다.

1. 적용 가능한 인덱스가 없는 경우
2. 인덱스 처리 범위가 넓은 경우 - DB가 인덱스를 적용해도 성능상 별 이점이 없다고 판단했을 때 Full Table Scan한다.
3. 크기가 작은 테이블에 엑세스하는 경우 - 2와 동일

Binary Search Tree (이진 탐색 트리)

 

 
이진탐색트리는 균형이 있다면 O(logN)으로 빠르게 탐색 가능하지만, 균형이 없을 때는 O(N)일 때도 있어서 이점을 얻지 못하는 경우가 있다. 이걸 극복하려고 나온게 B-Tree다.

B-Tree (Balanced Tree)

1. 트리의 높이가 같다.
2. 자식 노드를 2개 이상 가질 수 있다. 이진트리는 자식 노드가 최대 2개지만 B-tree는 최대 자식 수에 따라서 N차 B-tree라고 부른다.
3. 기본 데이터베이스의 인덱스 구조다.

 
Full Table Scan과 동일한 데이터를 B-Tree로 만든 다음 찾아보면 위처럼 7번 검색해서 찾을 수 있다. 즉 SELECT의 성능이 향상되는걸 볼 수 있다. 균일하지 못하고 한쪽에 노드가 다 치우진 이진트리에서 검색 시간복잡도가 O(N)으로 나올 수도 있는 것에 반해, B-tree는 어떤 값이라도 같은 시간에 결과를 얻을 수 있다는 균일성을 보장하는 균형 트리 개념이다.

 

그러나 B-tree도 생성 당시는 균형 트리지만 테이블 갱신(insert, update, delete)을 반복하면 서서히 균형이 깨지고 성능도 약화된다. 어느정도 자동으로 균형을 회복하는 기능이 있지만, 갱신 빈도가 높은 테이블에 작성되는 인덱스의 경우 인덱스 재구성을 통해 트리의 균형을 되찾는 작업이 필요하다.
 

 

Index에 의한 SELECT 성능, 그리고 INSERT, UPDATE, DELETE에 대해

 
먼저 INSERT에 대해 알아보자.
ZZZ를 삽입할 페이지가 이미 꽉 찼다면 빈 페이지를 하나 확보해서 거기에 넣고, 꽉 찼던 그 페이지의 데이터를 빈 페이지와 함께 공평하게 나눠서 저장한다. 이렇게 페이지 분할(페이지에 새로운 데이터를 채울 공간이 없어서 페이지에 무언가 변화가 생기는 것)이 발생하는 것은 부담이 되는 작업이기 때문에 DB가 느려지고 성능에 영향을 준다.
 
DELETE의 경우,
인덱스 데이터를 실제로 지우는 것이 아니라 사용안함 표시만 한다.
 
UPDATE의 경우,
변경하려는 기존 값을 사용안함으로 표시하고, 변경된 새 값을 삽입한다.
 

UPDATE, DELETE도 WHERE절을 사용하면(Index를 태우면) 더 빨리지는가?

• 좋은 점
  
  • WHERE 절로 처리할 대상을 찾아야 하는데 그 조회 성능은 향상된다.
• 나쁜 점
  • 인덱스 데이터를 지우는 게 아니라 사용안함 표시만 하고 데이터 자체는 계속해서 추가하니까 페이지를 낭비하게 되고 인덱스 조각화도 심해지며, 삭제 없이 지속적으로 추가하는 과정에서 페이지 분할도 많아질테니 성능이 저하된다.

따라서 인덱스는 SELECT 성능은 향상되지만 INSERT, UPDATE, DELETE는 성능이 저하된다.
 

인덱스의 종류

---

1. 클러스터링 인덱스
2. 논-클러스터링 인덱스 (보조 인덱스, 세컨더리 인덱스)

클러스터링은 무리를 의미하는 것으로, 클러스터링 인덱스라고 하면 실제 데이터와 같은 무리의 인덱스를 말한다. 실제 데이터 자체가 정렬되어 있는 사전 같은 게 클러스터링 인덱스에 해당된다.
 
논-클러스터링은 무리가 아니라는 말로, 논-클러슽어링 인덱스라고 하면 실제 데이터와 다른 무리의 별도 인덱스를 말한다. 책 뒤에 별도로 찾아보기 페이지가 제공되는 경우가 논클러스터링 인덱스에 해당된다.
 

Primary Key는 클러스터링, unique는 논-클러스터링 인덱스

 

클러스터링 인덱스를 만들면 어떻게 되는지

---

클러스터링 인덱스는 Primary Key로 지정하거나 Not Null, Unique 제약조건을 걸 때 생성된다.

클러스터링 인덱스 생성 방법: Primary Key 또는 Primary Key 없이 Not Null + UNIQUE 제약 조건 걸기

 
 
생성이 되면 아래와 같이 B-Tree가 생성된다.

클러스터링 인덱스 구성 후의 모습

 
루트페이지가 자식페이지를 가지고 있고, 위 그림처럼 리프페이지에는 실제 데이터를 가지는 데이터 페이지가 위치한다. 클러스터링 인덱스의 특징은 다음과 같다.

1. 실제 데이터 자체가 정렬되어 있다. ID 컬럼 기준으로 정렬되어 있었음.
2. 테이블당 1개만 존재 가능하다.
3. B-Tree의 리프페이지가 '데이터 페이지'다. (실제 데이터 페이지가 리프에 담겨있다.)
4. Primary Key를 걸거나, Unique + Not Null로 제약조건을 걸면 자동으로 클러스터링 인덱스가 생성된다.
   1. 둘이 같이 있으면 primary key가 우선순위를 가져가서 primary key로 인덱스가 생성된다.

 

논클러스터링 인덱스를 만들면 어떻게 되는지

---

논클러스터링 인덱스를 만들려면 아래와 같은 방법이 있는데, 방법3처럼 default INDEX를 만들면 중복을 허용하는 인덱스가 만들어진다.

 

 
클러스터링 인덱스는 데이터를 가진 데이터 페이지 자체가 B-Tree의 리프페이지가 되고 얘네들에 대해 루트 페이지가 만들어졌었는데, 논클러스터링 인덱스는 데이터 페이지는 그대로 있고 각 name에 대해 그 name을 가진 데이터 페이지를 찾을 수 있는 별도의 페이지가 리프 페이지로 추가된다. 이 name 을 가진 데이터가 '어느 페이지에 있는지(1002), 그리고 그 안에서는 어떤 주소에 있는지(#3)'를 가지는 B-Tree가 생긴다. 
 
여기서 '라라'를 찾는다면, '라라'는 도리와 스컬 사이에 있을 테니 100번이라는 리프 페이지로 이동하면 되고, 거기서 '라라'에 대한 정보가 1001번 * #2에 위치한다는 것을 알게 되므로 실제 데이터 페이지에 가서 1001번의 두번째 주소로 가면 데이터를 얻을 수 있다.
 
논클러스터링 인덱스의 특징은 다음과 같다.

1. 실제 데이터 페이지는 그대로
2. 별도의 인덱스 페이지 생성해야 하므로 추가 공간이 필요하다.
3. 테이블 당 여러 개가 존재할 수 있다.
4. B-Tree의 리프 페이지에는 실제 데이터 페이지가 아니라 데이터 페이지의 '주소'를 담고 있다. (뒤에 가면 달라진다. 실제론 주소를 들고 있는게 아님)
5. 한 컬럼에 unique 제약 조건을 적용하면 자동으로 논클러스터링 인덱스가 생성되고, 직접 index를 생성하는 경우에도 논클러스터링 인덱스가 생성된다.

클러스터링인덱스 (ID) + 논클러스터링인덱스(name에 대한 별도 인덱스)

---

SELECT * FROM MEMBER WHERE name = '라라';
를 한다고 할 때 아래 그림에서 왼쪽은 우리가 지금까지 본 예상한 그림이고, 실제 모습은 우측과 같다.

지금까지 예상한 그림 -> 실제 모습

예상으로는 name이 라라인 것에 대한 name에서의 별도 인덱스에서 리프 페이지를 통해 실제 데이터의 주소를 얻고, 그 주소에 가서 데이터 페이지를 찾지 않을까 했지만........
 
실제로는 name에 대한 인덱스들은 리프 페이지에 데이터가 들어있는 주소가 아니라 ID 값을 가지고 있다. 그래서 name에 대한 인덱스에서 B-Tree의 리프에서 ID를 얻고, 그 ID에 대해 클러스터링 인덱스 B-Tree를 타서 리프 페이지에 도착하는데, 여긴 리프 페이지 자체가 실제 데이터 페이지니까 이렇게 도달할 수 있다.
 
즉, 논클러스터링 인덱스는 리프 페이지에서 데이터 페이지의 주소를 가진게 아니라 ID를 가지고 있는 것이다.
 

왜 논클러스터링 인덱스가 데이터 페이지의 주소를 가지고 있지 않는걸까?

---

 
위에서 Index의 성능에서 언급했듯이, Insert나 Update에서(사용안함표시 때문에?) 값을 새로 추가하는데 여기서 페이지 분할이 일어난다고 했다. 그러면 데이터의 주소도 바뀌게 되니까 논클러스터링 인덱스가 리프 페이지에서 이 주소를 가지고 있어버리면 매번 주소 변경이 일어나야 한다. 이걸 막기 위해 논클러스터링 인덱스는 리프 페이지에서 클러스터링 인덱스가 적용된 컬럼의 실제 값 (Primary Key가 있다면 그 값, ID 같은 것)을 가지고 있다.
 

어느 컬럼에 인덱스를 적용해야 할까?

---

일단, 카디널리티( == 그룹 내 요소의 개수)가 높은 것. 즉, 중복도가 낮은 컬럼에 적용하는 게 좋다.

카디널리티는 ID, 이메일, 주민번호가 낮다. 중복이 별로 없어서.

 
그 외에도

• 카디널리티가 높은 컬럼. == 중복도가 낮은 컬럼
• where, join, order by 절에 자주 사용되는 컬럼 (인덱스는 조건 절이 있어야만 쓰이니까)
• insert, update, delete 가 자주 발생하지 않는 컬럼. (성능 저하 영향 때문에.)
• 규모가 작지 않은 테이블. (규모가 작으면 인덱스 효과가 미미하니까)

 

인덱스 보는 법

---

ID를 기본키로, email은 unique 제약 조건을 걸어서 인덱스를 만들었다.

 

• Non_Unique : 중복 허용이면 1, 허용 안하면 0.
• key name은 인덱스 이름. 기본키면 primary로 표시함.
• 카디널리티: 현재는 아무 데이터 없이 create table만 해놔서 0임.

 

정리

---

• 잘 활용되지 않는 인덱스는 과감히 제거하자.
  • Where 절에 쓰더라도 자주 사용되어야 가치가 있음.
  • 불필요한 인덱스로 성능 저하가 발생할 수 있다.
• 데이터 중복도가 높은 컬럼은 인덱스 효과가 적다.
• 자주 사용되더라도 insert, update, delete가 자주 일어나지는 않는지 고려해야 한다.
  • 일반적인 웹서비스 같은 온라인 트랜잭션 환경에서 쓰기와 읽기 비율은 2:8 또는 1:9다.
  • 조금 느린 쓰기를 감수하고 빠른 읽기를 선택하는 것도 하나의 방법이다.

 
출처
https://www.youtube.com/watch?v=edpYzFgHbqs