인덱스 구조란?
전의 포스팅에서 인덱스의 종류에 대해 알아보았습니다. 인덱스의 구조와 인덱스의 종류에 대해서 어떠한 차이가 있는 건지라는 질문이 나올 수 있다.
1. 인덱스의 구조
- 인덱스의 구조는 인덱스 데이터가 물리적으로 어떻게 구성되고 있는지에 대한 것이다.
- 예를 들어, B-Tree, Hash, R-Tree등은 인덱스의 데이터를 구조화하고 저장하는데 사용되는 알고리즘 또는 자료구조이다.
- 인덱스의 구조는 검색, 삽입, 삭 제 등의 연산을 어떻게 최적화 할 것인지 결정한다.
2. 인덱스의 종류
- 인덱스의 종류에는 인덱스가 어떤 목적 또는 특별한 사용 사례를 위해 설계되었는지를 나타냅니다.
- 예를 들어, 클러스터형 인덱스, 비클러스터형 인덱스, 비트맵 인덱스, 텍스트 인덱스 등은 인덱스의 사용 목적 또는 특성을 기반으로 분류된 인덱스의 종류이다.
- 즉, 인덱스의 종류는 데이터의 물리적인 저장 방식, 특정 쿼리 유형의 최적화, 특정 데이터 유형의 처리 방식 등에 따라 결정된다.
결론
간단히 말하면, "인덱스의 구조"는 "어떻게" 인덱스 데이터가 저장되는지에 관한 것이며, "인덱스의 종류"는 "왜"그러한 인덱스가 필요한지와 그 인덱스의 특별한 특성이 무엇인지에 관한 것이다.
클러스터형 인덱스와 보조 인덱스는 전에 보았듯이, 모두 내부적으로 B-Tree로 만들어진다.
B-Tree 구조
B-Tree 구조에서 데이터가 저장되는 공간을 노드라고 한다.
노드라는 용어는 개념적인 설명에서 주로 나오는 용어이고, MYSQL에서는 페이지라고 부른다.
루트 노드는 노드의 가장 상위 노드를 말한다. 모든 출발은 루트 노드에서 한다. 리프 노드는 제일 마지막에 존재하는 노드를 말한다. 루트 노드와 리프 노드의 중간에 끼인 노드들은 중간 노드라고 한다.
B-Tree는 데이터 검색을 할 때(==SELECT 구문을 사용할 때) 아주 뛰어난 성능을 발휘한다. 만약 아래 그림에서 MMM라는 데이터를 검색한다고 했을 때, 모두 리프 페이지만 있다면 MMM을 찾는 방법은 처음부터 검색하는 방법밖에 없다. 즉, 아까 위에서 보았던 FULL-Table-Scan해야 한다는 뜻이다.
이번에는 B-Tree에서 검색한다고 가정해보자. B-Tree는 무조건 루트 페이지부터 검색한다. 모든 데이터는 정렬되어 있고 MMM은 AAA,FFF,LLL 3개를 읽은 다음에 나오므로 세번째 리프 페이지로 직접 이동하면 된다. 세 번째 리프 페이지에서 LLL,MMM 2개를 읽어 MMM을 찾는다. 결국 루트 페이지에서 3개와 리프 페이지에서 2개, 합쳐서 5건의 데이터를 검색해서 원하는 결과를 찾았으며, 페이지는 2개를 읽었다.
FULL TABLE SCAN에서는 3개의 페이지를 읽었지만, B-Tree에서는 2페이지만 읽었다. 이는 데이터가 많을수록, 상당한 효과를 얻을 수 있다.
B-Tree의 페이지 분할
B-Tree가 그럼 장점만 있는 것은 아니다.
인덱스를 구성하면 데이터 변경 작업(INSERT, DELETE, UPDATE)시 성능이 나빠진다. 특히 INSERT 작업이 일어날 때 . 더 느리게 입력될 수 있다. 이유는 페이지 분할이라는 작업이 발생하기 때문이다.
페이지 분할이란 새로운 페이지를 준비해서 데이터를 나누는 작업을 의미한다. 페이지 분할이 일어나면, MySQL이 느려지고, 너무 자주 일어나면 성능에 큰 영향을 준다.
아까 그림에서 III가 새롭게 INSERT되었다고 가정해보자. 그러면 균형트리는 위의 사진과 같이 변경된다. 두 번째 리프 페이지에는 빈 공간이 있어서 JJJ가 아래로 한 칸 이동하고 III가 그 자리에 삽입된다. 정렬되어야 하기 때문에 JJJ가 한칸 이동한게 전부이기 때문에 큰 작업이 일어나지 않는 경우의 케이스이다.
그러면 여기서, GGG를 INSERT 한다면 어떻게 될까?
이럴 경우에는 새로운 페이지를 준비해서 데이터를 나누고 새로운 페이지를 루트에 등록해야하는 작업이 일어난다.
그러면 또 여기서, PPP,QQQ 2개를 연속해서 입력할 경우 어떻게 될까?
- PPP를 입력하면 4번쨰 리프 페이지에 빈칸이 있으므로 제일 마지막에 추가가 된다.
- 그 다음 QQQ를 넣으려고 하면, 4번째 페이지에 아까 PPP가 들어갔으므로 페이지 분할 작업이 일어난다.
- 추가된 5번째 리프 페이지를 루트 페이지에 등록하려고 하니, 루트 페이지도 꽉 찼다. 그래서 루트 페이지도 또한 분할을 해야 한다. 그리고 원래 있던 루트 페이지가 있던 곳은 2개의 페이지가 되어서 루트 페이지가 아닌 중간 페이지가 된다.
- 마지막으로 새 페이지를 준비해서 중간 노드를 가리키는 새로운 루트 페이지를 구성해야 한다.
결국 QQQ 하나를 입력하기 위해서 3개의 새로운 페이지가 할당 되고, 2회의 페이지 분할이 일어났다.
데이터 하나를 입력하기 위해 너무 많은 일이 일어난 것이다. 즉,입력 작업이 엄청 오래 걸렸다는 의미이다.
이것이 B-Tree구조의 단점이다. 즉, select를 제외한 Update, create시에 입력 작업이 오래 걸린다.
인덱스의 구성
1. 클러스터형 인덱스 구성하기
CREATE TABLE CLUSTER(
mem_id char(8),
mem_name varchar(10)
);
실제로는 1페이지에 16KB이라서 많은 데이터가 입력되지만, 현재는 1페이지에 4개의 데이터만 입력된다고 가정하고 상황을 진행하겠습니다.
인덱스가 없어서 데이터가 INSERT된 순서대로 저장이 된다.
이제 테이블의 mem_id에 클러스터형 인덱스를 구성해보자.
alter table cluster
add contraint
primary key (mem_id);그리고 다시 select하면 mem_id 기준으로 오름차순 정렬이 되어 있다. 앞에서 본 것처럼 클러스터형 인덱스가 생성되었기 때문이다.
실제 데이터는 페이지가 정렬되고 B-TREE형태의 인덱스가 형성된다.
먼저 클러스터형 인덱스를 구성하기 위해 행 데이터를 지정한 열로 정렬한다. 그리고 각 페이지의 인덱스로 지정된 열의 첫번째 값을 가지고 루트 페이지를 만든다.
루트 페이지는 C언어로 비유하자면 포인터와 같고 리프 페이지는 그 포인터가 가리키는 실제 값을 의미한다.
2. 보조 인덱스 구성하기
아까와 동일한 데이터로 보조 인덱스를 만들어보자.
CREATE TABLE SECOND(
mem_id char(8),
mem_name varchar(10)
);고유 키 제약 조건은 보조 인덱스를 생성하므로 mem_id 열에 unique를 지정하고 데이터를 확인해보자.
alter table second
add contraint
unique (mem_id);보조 인덱스가 생성되어도 데이터의 순서는 입력한 것과 동일하다.
보조 인덱스는 데이터 페이지를 건드리지 않는다.
그리고 위의 그림처럼 별도의 장소에 인덱스 페이지를 생성한다.
우선 인덱스 페이지의 리프 페이지에 인덱스로 구성한 열을 정렬한다. 일반 책의 찾아보기를 보면 ABC또는 가나다 순서로 정렬되어 있는 것과 마찬가지이다. 그리고 실제 데이터가 있는 위치를 준비한다.
데이터 위치는 페이지 번호 +#위치로 기록되어 있다. APN을 보면 1001페이지의 4번째에 데이터가 있다고 기록한다.
인덱스에서 데이터 검색하기
1. 클러스터형 인덱스에서 데이터 찾기
SPC를 검색한다고 가정해보자.
1. 루트 페이지(100번)을 읽어야 한다. SPC는 알파벳 순서로 따지면 MMU와 TWC사이이므로 MMU가 가리키는 리프 페이지의 1001번으로 이동한다.
2. 리프 페이지를 읽으니 네번째에 찾고자 하는 값이 있다.
클러스터형 인덱스에서는 2개 페이지를 읽어서 SPC의 이름을 알아냈다.
- 보조 인덱스에서 데이터 찾기
이번에는 보조 인덱스에서 SPC 회원의 이름을 검색해본다고 가정해보자. SPC를 검색할 때는 인덱스 페이지의 루트 페이지(10번), 리프 페이지(200번), 그리고 데이터 페이지를 읽어서 SPC의 이름을 알아냈다.
총 3개의 페이지를 읽어서 SPC의 이름을 알아냈다.
일반적으로는 클러스터형 인덱스가 보조 인덱스보다 검색 속도가 빠르다.
