1.클러스터형

DB 엔진이 인덱스를 어떤 식으로 관리하고 쿼리문에서 인덱스를 어떻게 활용하는지 내부적인 관리 방식과 동작 체계에 대해 연구해 보자. 내부 동작을 엿보는 것이기 때문에 복잡하고 어렵지만 완전히 다 이해할 필요는 없고 대충 훓어만 보면 된다. 이 실습은 클러스터형과 넌클러스터형의 구분이 뚜렷한 MSSQL에서 수행하되 오라클, 마리아도 내부 저장구조는 B-Tree여서 동작 원리는 거의 동일하다.

먼저 클러스터형 인덱스부터 살펴 보자. DROP TABLE 명령으로 앞 절에서 만들었던 tArtist 테이블을 제거하고 다음 쿼리문으로 테이블을 생성하면 기본키가 지정된 name 필드에 대해 클러스터형 인덱스를 생성한다. 인덱스가 있다고 해서 겉으로 드러나는 차이점은 없어 굳이 실습을 같이 할 필요는 없다. 귀찮으면 구경만 해 봐도 상관없다.

CREATE TABLE tArtist

(

name CHAR(12) PRIMARY KEY,

age INT,

addr VARCHAR(30)

);

테이블을 생성한 후 샘플 데이터도 다시 삽입한다. 이제 name에 중복 이름은 금지되어 동명이인을 입력할 수 없다. 이 테이블의 저장 구조는 다음과 같다. 편의상 데이터 페이지당 레코드는 4개씩만 들어가고 인덱스 페이지에는 7개가 들어간다고 가정한다.

클러스터형 인덱스가 있어 레코드를 이름순으로 정렬하여 저장한다. 가나다순으로 가장 빠른 고소영이 선두에 오고 다음으로 김태희, 문근영을 순서대로 기록하며 한 페이지가 가득 차면 다음 페이지에 계속 기록한다. 루트의 인덱스 페이지에는 각 데이터 페이지의 선두 레코드 키값과 페이지 번호를 기록한다.

데이터 페이지가 정렬되어 있더라도 별도의 인덱스 페이지가 필요한 이유는 데이터 페이지가 반드시 인접해 있다는 보장이 없기 때문이다. 삽입, 삭제를 반복하다 보면 페이지가 흩어져 레코드가 어느 페이지에 있는지 위치를 기록해 두어야 한다. 인덱스 페이지를 보면 레코드의 위치와 순서를 알 수 있다. 그래서 클러스터형 인덱스도 별도의 공간을 차지한다. 테이블이 아주 클 때는 인덱스 페이지도 여러 개로 분할된다.

이 상태에서 문근영을 찾아 보자. 우선 인덱스 페이지에서 문근영이 포함된 페이지를 찾는다. 문근영은 고소영보다는 크고 배용준보다는 작아 고소영이 속한 1페이지에 있음을 알 수 있다. 1페이지를 읽어들여 이 안에서 이분 검색으로 문근영을 찾는다. 인덱스로부터 페이지를 찾아 그 페이지만 뒤지면 원하는 레코드를 찾을 수 있다.

검색 속도는 환상적이다. 레코드가 아무리 많아도 이 과정에는 별 차이가 없으며 속도도 거의 일정하다. 하지만 삽입 및 삭제할 때는 데이터 페이지의 정렬 상태를 유지하기 위해 제 위치를 찾아서 넣어야 하므로 복잡해진다. 게다가 페이지에 여유 용량이 없을 경우 페이지 분할까지 해야 한다. 이 상태에서 김희선 레코드를 삽입해 보자.

김희선은 김태희보다는 크고 문근영보다는 작아 이 둘 사이에 끼어든다. 그런데 김희선이 들어가야 할 첫 번째 페이지가 꽉 차 레코드를 더 삽입할 수 없다. 이때 페이지 분할이 발생한다. 새 레코드가 들어갈 공간을 만들기 위해 첫 번째 페이지를 두 개로 분할한다. 페이지 분할 과정은 세포 분열과 흡사하다.

새 페이지를 할당하고 기존 페이지의 레코드를 절반씩 나누어 준다. 소영이와 태희는 원래 페이지에 남고 근영이와 신양이는 새로 할당된 페이지로 이사간다. 레코드를 절반씩 분할하는 이유는 양쪽에 빈칸을 공평하게 나누어 다음 삽입시 가급적 페이지 분할이 발생하지 않도록 하기 위해서이다. 분할 후 김희선이 자기 위치인 두 번째 페이지의 선두(또는 첫 번째 페이지의 끝)에 들어간다.

인덱스 페이지에도 노드를 분할했다는 것을 기록한다. 새로 생성한 페이지에 4번이 부여되고 김희선이 선두임을 기록했다. B 트리 구조는 링크에 의해 페이지가 연결되므로 페이지 번호는 연속적일 필요 없다. 기존의 2, 3 페이지는 특별히 손 델 필요없이 그대로 유지하면 된다. 최종적으로 완성된 모양은 다음과 같다.

어떤 경우에는 연쇄적으로 분할이 발생하기도 하고 인덱스 페이지에 더 기록할 공간이 없으면 여기서도 페이지 분할이 일어난다. 이렇게 되면 인덱스 페이지의 위치를 가리키기 위한 새로운 상위 인덱스 페이지를 생성한다.

레코드 하나 삽입에 의해 내부에서는 대규모의 공사가 일어날 수 있다. 그렇다고 해도 분할된 페이지 외에 앞 뒤의 페이지는 전혀 영향을 받지 않아 배열보다는 월등히 빠르다. 용준이와 지현이가 있는 페이지는 희선이가 들어오기 전의 상태 그대로이다.

또 페이지 분할이 항상 발생하는 것도 아니다. 이 상태에서 박진희를 삽입한다고 해 보자. 자기 위치인 박신양 뒤에 빈 공간이 남아 있어 그냥 써 넣기만 하면 된다. 이런 이점이 있기 때문에 페이지의 뒤쪽을 가득 채우지 않고 가급적이면 적당히 여유 공간을 남겨 둔다.

마찬가지로 레코드를 삭제할 때도 그냥 지우기만 하고 당기지는 않는데 빈칸을 조만간 재사용할 수도 있어 굳이 당길 필요가 없다. 장동건을 삭제한다고 해서 전지현을 굳이 2페이지 끝으로 옮길 필요가 없다. 클러스터형 인덱스가 생성되어 있는 열은 검색도 빠르지만 정렬도 엄청나게 빠르다. 이름순으로 레코드를 정렬하는 명령을 내렸다고 해 보자.

SELECT * FROM tArtist ORDER BY name;

인덱스 페이지를 순서대로 읽으면 각 페이지를 찾을 수 있다. 이제 이 페이지를 순회하며 레코드를 읽어 뿌리기만 하면 된다. 데이터 페이지가 이름순으로 가지런히 정렬되어 있고 데이터 페이지의 순서는 인덱스 페이지에 기록되어 있어 그야말로 거저 먹기다. 범위 검색에도 유리하다.

SELECT * FROM tArtist WHERE name BETWEEN '문근영' AND '장동건';

문근영 찾고, 장동건을 찾으면 그 중간의 레코드는 모두 조건에 해당된다. 문근영과 장동건 사이의 레코드를 순서대로 읽어 결과셋에 뿌리면 된다. 이래서 인덱스가 좋은 것이다.