인덱스

데이터베이스에서 쓰이는 인덱스에 대해 알아보자. 

인덱스란?

인덱스는 데이터베이스에서 데이터 검색(SELECT) 속도를 높이기 위해 사용되는 자료구조다. 

인덱스 장점 

• SELECT (조회) 성능 향상

인덱스 단점

• 대략적으로 테이블의 10% 추가 공간 필요
• INSERT, UPDATE, DELETE가 자주 발생하면 성능에 악영향 

인덱스 종류 

클러스터형 인덱스 

• 테이블 당 1개만 생성 가능 
• PK 컬럼에 대해 자동 생성 
• 리프 노드가 실제 데이터 레코드를 포함
  • 따라서 실제 데이터 레코드는 클러스터형 인덱스 키 순서대로 정렬

보조 인덱스

• 한 테이블에 여러개 생성 가능 
• UNIQUE 제약 조건 컬럼에 대해 자동 생성 
• 리프 노드가 실제 데이터 레코드의 위치 포함
• 보조 인덱스 자체는 키에 대해 정렬됨

동작 원리 

일반적으로 클러스터링 인덱스, 보조 인덱스 모두 B+ tree 구조를 사용한다.

B Tree

B+ Tree는 B Tree를 개선한 것이므로 먼저 B Tree가 무엇인지 알아보자.

• 이진트리를 개선한 자료구조다.
• 부모 노드가 자식 노드를 2개 초과해서 가질 수 있다.
• 하나의 노드가 여러개의 키 값을 가질 수 있다

균형잡힌 트리

B Tree는 이진 트리와 달리 균형잡힌 형태의 트리다.  

균형이 쏠린 이진트리

이진트리에서 노드의 균형이 한 쪽으로 쏠리면 길이가 N인 리스트와 같은 구조가 되며 탐색 시 최악시간복잡도가 O(N) 이 된다. 

반면 B Tree는 균형을 유지하기 때문에 N개의 노드에 대해 길이가 최대 log(N)으로 제한된다. 따라서 탐색 시 O(logN)의 시간복잡도를 갖는다. 

B+ Tree

인덱스 구현에는 B Tree가 아닌 B+ Tree가 쓰인다고 했는데, B+ Tree와 B Tree를 비교해보자.

• 데이터 저장 위치
  • B Tree : 내부 노드 또는 리프 노드에 데이터 저장 
  • B+ Tree : 리프 노드에만 데이터 저장  

• 리프 노드 간 연결 
  • B Tree : 리프 노드간 연결이 없음
  • B+ Tree : 리프 노드들이 LinkedList 형태로 연결됨. 범위 검색, 순차 접근 등에 유리함 
• 키 중복 
  • B Tree : 키 값 자체가 데이터이며, 중복을 허용하지 않음
  • B+ Tree : 내부 노드의 키는 리프 노드의 데이터를 가리키는 역할만 하며 중복될 수 있음 

B+ Tree는 데이터가 리프 노드에만 있기 때문에 탐색 시 리프 노드까지 탐색해야 한다. 따라서 하나의 데이터를 탐색할 때는 B Tree가 더 빠르지만, 범위 검색 (순차데이터 검색) 등의 경우 리프 노드에서 linkedlist를 활용해 검색할 수 있어서 B+ Tree가 더 빠르다. 

 

다른 자료구조들에 비해 B+ Tree의 장점

Array

배열은 데이터의 물리적 위치 = 논리적 위치로 접근이 빠르다. 하지만 삽입, 삭제시 마다 주변 모든 데이터를 shift 하기 때문에 O(N)의 시간복잡도가 발생한다.

LinkedList

LinkedList는 삽입, 삭제가 용이하지만, 탐색 시 무조건 head 부터 시작해야 해서 탐색이 빈번한 데이터베이스에 부적절하다. 

Hash

Hash는 Key-Value의 구조로 탐색 시 O(1)의 시간복잡도를 갖는다.  하지만 데이터베이스에서 자주 쓰이는 범위 검색이 어렵다.

 

클러스터형 인덱스 페이지 구조

인덱스는 루트-중간-리프 페이지로 구성된다. 클러스터형 인덱스에서 리프 노드는 실제 데이터 페이지가 된다. 루트 노드에서 탐색할 페이지를 찾고 해당 페이지에서 검색할 데이터를 찾는다.

 

보조 인덱스 페이지 구조 

보조 인덱스의 리프 노드는 실제 데이터가 아닌 데이터의 위치를 저장한다. 예를 들어 103 리프노드의 3번째 값은 id=11 인 데이터 위치 102+#4를 가리키고 있으며 데이터 페이지에서 102 노드의 4번째를 확인하면 id=11 인 데이터를 확인할 수 있다.

유의사항

• 중복도가 낮은 컬럼에 생성할 것 
  • 중복도가 높은 컬럼에 생성 시 성능 향상이 미미함 
• WHERE 절에 자주 사용되는 컬럼에 생성할 것
• 잘 사용되지 않는 인덱스는 제거 
  • 인덱스도 저장공간을 차지하고, SELECT 외에는 성능 저하를 일으킬 수 있다. 
• INSERT, UPDATE, DELETE 등의 작업이 빈번한 테이블에서는 인덱스 사용 고려 
  • 인덱스는 정렬된 상태를 유지하므로 인덱스 또한 삽입, 갱신, 삭제 후 정렬해야 한다. 

인덱스 예시

생성, 삭제

CREATE TABLE member (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    job VARCHAR(30),
    age INT NOT NULL,
    register_id INT UNIQUE
);

SHOW INDEX FROM member;

테이블을 생성하고 show index from member 로 자동생성된 인덱스를 확인해보자. 

key_name 이 PRIMARY 인 인덱스가 클러스터형 인덱스로 PK에 의해 자동 생성된 것이고, UNIQUE 컬럼인 register_id에 의해 보조 인덱스도 자동 생성되었다. 

create unique index job_idx
on member (job);

ANALYZE TABLE member;

SHOW INDEX FROM member;

create index 문으로 인덱스를 생성해보겠습니다. 생성 후 analyze 로 적용해주어야 합니다. 

job_idx 인덱스가 생긴 것을 확인할 수 있습니다.

drop index job_idx on member;
ANALYZE TABLE member;
SHOW INDEX FROM member;

다시 인덱스를 삭제해보자. 

내가 만든 인덱스는 drop 을 통해 삭제할 수 있다. 다만 자동생성된 인덱스는 삭제할 수 없고 alter 를 통해 테이블 자체를 수정해주면 알아서 삭제된다. 

사용

인덱스를 사용하고 실제로  사용되는지 확인해보자. 

create table user
(
id bigint primary key auto_increment,
room_no int,
name varchar(30)
);

위의 user 테이블에 대해 인덱스를 사용해보자.

explain analyze
select *
from user
where id>10;

결과
-> Filter: (`user`.id > 10)  (cost=4.26 rows=20) (actual time=0.0152..0.0266 rows=20 loops=1)
     -> Index range scan on user using PRIMARY over (10 < id)  (cost=4.26 rows=20) (actual time=0.0134..0.0238 rows=20 loops=1)

pk에 의해 자동생성된 클러스터형 인덱스를 사용해보자. where 절에 id 컬럼조건을 넣어주자 분석 결과 index range scan 을 한 것을 확인할 수 있다. 

explain analyze
select room_no
from user
where room_no>300; 

결과
-> Filter: (`user`.room_no > 300)  (cost=6.25 rows=20) (actual time=0.14..0.168 rows=40 loops=1)
     -> Table scan on user  (cost=6.25 rows=60) (actual time=0.13..0.153 rows=60 loops=1)

인덱스가 없는 roon_no 컬럼에 대해 where 조건을 걸어보자. 분석 결과 Table scan 즉 테이블의 모든 row를 검색해서 조건을 검사했다. 

create unique index room_no_idx
on user(room_no);

analyze table user;

show index from user;

이번에는 user 테이블에 room_no  컬럼에 대한 보조 인덱스를 생성해주었다. 

explain analyze
select room_no
from user
where room_no>300; 

결과
-> Filter: (`user`.room_no > 300)  (cost=8.28 rows=40) (actual time=0.0435..0.0876 rows=40 loops=1)
     -> Covering index range scan on user using room_no_idx over (300 < room_no)  (cost=8.28 rows=40) (actual time=0.039..0.0774 rows=40 loops=1)

Covering index range scan 즉 인덱스를 활용해 검색했고 actual time도 0.0435..0.0876 으로 감소했다. (cost=8.28 rows=40) 에서 rows는 예상 rows다. 예상 rows를 인덱스를 토대로 예상했기 때문에 실제 실행 결과 actual rows인 (actual time=0.0435..0.0876 rows=40 과 같은 값을 예상했다. 반면 인덱스가 없을 떄의 예시에서는 예상 rows가 20인 것을 확인할 수 있다. 

explain analyze
select `name`
from user
where room_no>300;

-- 결과
drop index room_no_idx on user;
-> Filter: (`user`.room_no > 300)  (cost=6.25 rows=40) (actual time=0.0577..0.0855 rows=40 loops=1)
     -> Table scan on user  (cost=6.25 rows=60) (actual time=0.0524..0.075 rows=60 loops=1)

이번에는 where 절에 room_no를 사용했지만 table scan을 했다.  이유는 select 절에 name을 검색하기 때문에 어차피 실 데이터를 확인해야 한다. 따라서 인덱스 사용 보다는 mysql이 table scan의 성능이 더 낫다고 판단한 것이다. 이처럼 where 절에 인덱스가 있는 컬럼을 사용했다고 무조건 그 인덱스를 사용하는 것이 아니라, 데이터베이스 엔진이 더 효율적이라고 판단한 방식을 선택한다. 

explain analyze
select `name`
from user
where id>30;

-- 결과
-> Filter: (`user`.id > 30)  (cost=12.3 rows=60) (actual time=0.0733..0.145 rows=60 loops=1)
     -> Index range scan on user using PRIMARY over (30 < id)  (cost=12.3 rows=60) (actual time=0.0641..0.127 rows=60 loops=1)

where 절에 pk, 즉 클러스터형 인덱스가 있는 id 컬럼을 사용하자 index range scan을 한다. 클러스터형 인덱스는 리프 노드에 실제 데이터를 갖고 있기 때문에 select 절에서 name을 검색해도 인덱스를 사용해 효율적으로 검색할 수 있기 때문이다. 

 

이처럼 인덱스가 있다고 무조건 사용되는 것이 아니고, 데이터베이스 엔진의 판단에 따라 더 효율적인 방법을 사용하므로 인덱스와  쿼리를 잘 세팅해야 원하는 효과를 얻을 수 있다. 

출처

https://velog.io/@ann9902/BTree%EB%A5%BC-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EC%97%90-%EC%82%AC%EC%9A%A9%ED%95%98%EB%8A%94-%EC%9D%B4%EC%9C%A0#b-tree%EC%9D%98-%ED%8A%B9%EC%A7%95

B+Tree를 인덱스에 사용하는 이유

https://rachel0115.tistory.com/entry/MySQL-%EC%9D%B8%EB%8D%B1%EC%8A%A4-INDEX-%EC%A0%95%EB%A6%AC-%EB%8F%99%EC%9E%91-%EB%B0%A9%EC%8B%9D-%EC%83%9D%EC%84%B1-%EC%82%AD%EC%A0%9C-%EC%84%A4%EA%B3%84

[MySQL] - 인덱스 (INDEX) 정리 (동작 방식, 생성, 삭제, 설계)