1 인덱스의 개념

2 인덱스의 재정렬의 개념

3 인덱스를 이용한 검색

4 Sparse Index & Dense Index & Heap

5 상용 DBMS별 Index 종류

6 Index 공간 절약을 위한 압축

7 Heap과 트랜잭션 그리고 MSSQL Server

8 Hot Table의 인덱스와 데이터 분리

인덱스는 검색의 효율성을 높이기 위한 물리적인 데이터 구조다. 보통 인덱스를 설명하자면 책의 목차나 찾아보기의 예를 들고 있다. 우리는 특정한 키워드에 대한 내용이 책의 몇 페이지에 있는지를 찾기 위해서 책 뒷부분의 찾아보기를 찾아 해당 페이지를 쉽게 찾을 수 있다. 만약 찾아보기나 목차가 없었다면 우리는 책을 처음부터 끝까지 뒤져야 한다. 만약 그 키워드가 책에서 딱 한 부분에서만 설명된다는 보장이 있다고 가정하자. 운이 있으면 몇 페이지 뒤지지 않고도 해당 내용을 찾을 수 있다. 하지만 해당 키워드가 책의 여러 분산된 페이지에서 다루는 내용이라면 우리는 책을 끝까지 뒤져야 한다.

그렇다면 내용이 추가된 경우는 어떻게 해야 할까? 내용이 추가되기 전의 목차는 다음과 같을 것이다.

1. 데이터베이스 기초
   
2. 데이터 모델링
   
3. SQL
   
4. ...
   
   

만약 1과 2사이에 '프로세스 모델링'이라는 단원이 추가된다면 '데이터 모델링'이후부터는 모두 숫자를 바꾸어야 한다. 책의 뒤는 어떠한가? 찾아보기도 추가되어 다시 정렬해야 한다. 만약 3장 SQL이 삭제되면 어떠한가? SQL 뒤에 있는 다른 Chapter는 모두 다시 번호를 매겨야 한다. 데이터베이스의 인덱스는 이와 거의 비슷하다. 인덱스 자체도 물리적인 구조이다.

아래의 숫자들을 이용해서 무작위로 선정해서 인덱스[1]에 삽입하도록 하겠다. 어떻게 재정렬되는지 살펴보자.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

박스의 오른쪽 귀퉁이를 보면 필자가 임의로 삽입한 숫자다. 그리고 값의 양 옆에 보이는 것은 포인터 인데 이 포인터는 항상 키 값보다 1개 더 존재한다. 여기서 포인터의 개수를 차수라고 한다. 무작위로 숫자를 B-Tree로 만든 것에 대한 설명을 해보도록 하겠다.

구체적인 정렬 알고리즘을 모두 알고 있으면 좋겠지만, 이런 내용까지 언급한 이유는 인덱스를 관리하는데는 비용이 든다는 것을 알아줬으면 하는 데에 있으므로 부디 짜증내지 말기 바란다.

삽입은 약간 복잡하다. 자세한 사항은 파일구조에 관련된 전문서적을 보아야 할 것이다. 이제 검색에 대해서 살펴보겠다. 검색은 개념이 아주 쉽다. 위에서 1~10 까지 삽입된 B-Tree를 가지고 검색에 대해서 살펴보겠다. 7을 찾는다면 어떻게 찾아야 할까?

지금은 이러한 B-Tree는 잘 쓰지 않고, 여기서 약간씩 변형된 B+-Tree(B- Plus Tree)나 B*-Tree(B- Star Tree)를 많이 사용합니다. 여러분은 이러한 것들에 대해서 알아야 할 필요가 있다. 자세한 것은 관련 서적을 따로 봐야 할 것이다. 인덱스는 검색을 위한 메커니즘이다. 삽입에서 살펴보았듯이 검색보다는 갱신/삭제/삽입은 많은 비용이 드는 일이다. 하지만 갱신/삭제은 원하는 적은 양의 데이터만을 변경하는 것이므로 인덱스를 이용하는 것이 인덱스를 이용하지 않을 때보다도 효과적이다. 대부분의 어플리케이션이나 사용자는 검색을 주로 하기 때문[2]에 인덱스의 사용은 거의 필수적이라고 할 수 있다. 물론 갱신과 삭제도 검색이 일어난 후에나 가능하다.

참고

B-Tree는 30여년 된 이론이다. B-Tree는 메모리에 적재하기엔 너무 큰 인덱스에 대한 고찰로부터 출발한다. 필자가 보기엔 이 B-Tree가 없었다면 지금 필자도 데이터베이스를 할 수 있었을까? 하는 의문을 가지게 하는 감동스러운 것이다. B-Tree에서 ‘B’의 약자는 무진장 애매모호하다. Binary는 아니지만 그렇다고 Bushy, Borad, Balanced, Bayer 등 주장하는 바가 많다. 여기서 Bayer는 McCreight와 함께 B-Tree 논문을 발표한 사람인데, 기념하기 위해서 단위등에 발견하거나 이론을 처음 발표한 사람의 이름을 남기기 위해서 쓰이기는 하지만 밝혀진바는 없다. 참고로 Bayer와 McCreight는 ‘B’에 대한 언급을 한 적이 없다.

일반적인 DBMS에서는 다음 3가지의 데이터 구조를 가진다.

• Sparse Index:해당 레코드 존재 페이지를 가리키는 포인터를 저장
  
• Dense Index:해당 레코드를 가리키는 포인터를 저장
  
• Heap : 데이터가 입력되는 순서에 따라 정렬되어 쌓이는 테이블 구조
  
  

페이지에는 여러 개의 레코드가 있으므로 일반적인 경우는 스파스(Sparse)인덱스가 유리하다. 하지만 레코드의 길이가 페이지의 크기와 비슷한 경우라면 스파스 인덱스는 덴스 구조보다 디스크 액세스를 많이 수행하게 되므로 성능이 떨어진다. 물론 조건은 있다. DBMS가 어떻게 구성되었느냐에 따라 틀리다. 만약 해당 DBMS에서 데이터 행 체인(Row Chain)이 발생된다면 불리할 수 있으나 체인을 지원하지 않고, 행 마이그레이션(Row Migration)만 지원한다면 큰 차이가 없다. 어떤 DBMS는 최소 입/출력 단위에 데이터를 꽉꽉 채울 수 있는 반면, 어떤 DBMS는 데이터를 모두 채울 수 없기 때문에 두 인덱스 방식의 장/단점의 비교는 조건이 잘 주어져야 가능하다.

상용 DBMS는 다음과 같은 종류를 인덱스를 가지고 있다. Oracle에서는 인덱스 조직 테이블(Indexed-Organized Table)이라고 해서 MSSQL Server의 클러스터드 인덱스를 가진 테이블과 비슷한 구조로 생각하면 되는데, 이는 Sparse Index 방식이라고 보면 된다.

DBMS	Primary Data Structures	Secondary Data Structures
IBM DB2 UDB	B-Tree(D)	B-Tree
Oracle	B-Tree(D), Hash(D)	B-Tree, Bitmap, Function
MSSQL	B-Tree(S)	B-Tree
Sybase	B-Tree(S)	B-Tree

또 한 가지 중요한 사실은 Sparse Index (Primary Index)와 Dense Index (Secondary Index)가 혼재되어 있을 경우 Disk에 따로 나누어 저장하는 것인 효과적이라는 것이다.

DBMS가 사용하는 전형적인 압축기법은 프리픽스 압축(Prefix Compression) 기법이다. 프리픽스 압축 기법은 인접한 노드들의 키를 구분할 수 있게 압축하는 방법으로 저장 공간을 절약한다. 또한 Oracle에서는 프론트 압축(Front Compression)이라는 기법을 사용한다. 두 압축 기법은 다음의 그림을 보면 알 수 있다.

데이터베이스 시스템에서 빼놓지 않고 중요하게 언급되는 사항은 트랜잭션이다. 작은 트랜잭션 하나가 잠금을 얻으면 잠금 수준에 따라서 많은 양의 트랜잭션이 대기할 수도 있다. Heap과 같은 구조는 데이터가 들어오는 순서대로 쌓이기 때문에 특정 페이지(최소 입/출력 단위) 잠금이 걸린다면 해당 페이지에 접근하고 있는 트랜잭션은 모두 대기 상태가 된다. 이러한 경우 레코드 단위의 잠금을 걸면 해결되지만, 레코드의 입력이 너무 빈번히 발생한다면, 결국 병목현상이 발생하게 된다. 그러므로 MSSQL Server와 같은 경우는 테이블에 클러스터드 인덱스(Sparse Index)를 생성하기를 권장하고 있다.

하지만 클러스터드 인덱스는 Insert, Update, Delete시에 데이터를 재정렬(데이터도 페이지 분할에 의해 일부 이동하지만 대부분은 페이지 연결 리스트 갱신이다)해야 하므로 Insert, Update, Delete시에는 부하(데이터 페이지의 더블 링크드 리스트의 헤더, 테일을 바꿀 뿐이다)가 있다. 범위 연산이나 한 번에 많은 데이터를 가져와야 하는 경우라면 클러스터드 인덱스를 생성해야 한다. 일반적인 OLTP시스템이라면 클러스터드 인덱스는 권장사항이다. 그러나 특정 행 단위 위주로 접근하는 경우라면 클러스터드 인덱스는 권장사항이 아니다. 조회 성능이 매우 중요하다면 클러스터드 인덱스 생성은 적극 고려해야 할 대상이다.

만약 시간이 된다면 주로 쓰이는 인덱스의 순서에 맞추어 테이블의 데이터를 다시 넣는 작업을 하면 성능상 도움이 된다. 또한 Insert, Update, Delete시 인덱스도 같이 변경되어야 하므로 MSSQL Server는 PAD_INDEX, FILLFACTOR옵션을 인덱스 생성, 변경 시 제공하고 있다. 이 두 옵션은 인덱스의 저장 공간을 비워두어 추가적인 작업(Insert 등)에 대해 인덱스의 재조정을 막기 위한 것이다.

Hot Table이란 동시에 트랜잭션의 처리가 매우 빈번히 발생하는 테이블을 말한다. 데이터의 Insert, Delete가 집중적으로 수행되면 논클러스터드 인덱스 유리하다. 또한 Table과 Index를 물리적으로 다른 Disk에 배치하면 성능이 향상된다. 왜냐하면 거의 모든 읽기와 입력은 인덱스를 이용하여 처리되기 때문에 인덱스 구조 유지 비용 분산을 분산시켜주기 때문이다.

안녕하세요.
인덱스의 구조를 공부하기위해 들렸다가 좋은글 감사히 보았습니다.
클러스터 인덱스의 리프노드의 값들이 "데이터페이지"를 가리키고,
비클러스터 인덱스는 리프노드의 값들이 "행을 가리키는 주소값"을 가지고 있는것으로 이해를 하였습니다.

문의드리고 싶은것이 있는데,
"랜덤 엑세스"라는 것은 순차적 페이지 호출(i/o)이 아닌 '한 건의 레코드 단위'로 접근하여 페이지단위로 호출하는것을 뜻하는 것인가요?
제가 이해하고 있는것이 맞다면, 랜덤 엑세스라는 것은 리프노드가 페이지를 가리키는 클러스터 인덱스에서는 발생하지 않는 것이 맞는 것인지 궁금합니다.

그리고 마찬가지로, 클러스터 인덱스의 리프 노드가 데이터 페이지(레코드가 100건이라고 가정)를 가리킨다면
행의 주소값이 없어 접근을 할수 없으니 1건의 레코드를 출력하기위해서는 100건의 레코드 페이지를 불러와서 검색한 다음 출력해야하나요?

인터넷에 널린 자료들마다 작성자가 달라서인지
같은 인덱스에도 다른 설명이 많아서 더 헷갈리는 것 같습니다.
가르침을 부탁드리겠습니다.
감사합니다. -- 봉봉이 2014-06-30 23:39:38

궁금한점이 잘 해결되지않아서 "index seek" 문서를 읽어보고왔습니다. (댓글이 수정이 안되네요.ㅠㅠ)
북마크 룩업이란것은 애초에 커버드 인덱스가 아닐때 데이터페이지로 접근 하는 과정이 북마크 룩업으로 알고있는데
작성해주신 글을보니, 랜덤 엑세스 = 북마크룩업의 내용으로 작성을 하셨더라구요.

그렇다면, 랜덤 엑세스라는 것은 비클러스터 인덱스에서만 나타나며
" '인덱스에 존재하지 않는 컬럼의 값을 찾기위해' 레코드주소로 데이터 페이지에 접근하여 호출함으로 인해 별도의 추가 i/o가 발생하는 것"을 의미하는 것인가요?
아니면 그냥 데이터페이지접근이 아닌 레코드주소로 접근하여 발생하는 i/o를 통틀어서 그냥 랜덤 엑세스라고 하는건인가요?

위의 질문과 같이 남겨봅니다. ^^;; 번잡하게해드려 죄송합니다. -- 봉봉이 2014-07-01 01:39:53

트리 공부하다가 들렸는데 정리가 잘 되어있어서 잘 배우고 갑니다! -- 대학원생 2019-02-20 11:38:57