[MSSQL] 인덱스의 내부 동작 방식

SQL Server 의 내부 데이터 관리 방식

  내용의 이해를 위해서는 SQL Server의 데이터 관리방식의 글을 읽어 보시고 오시면 

  이해를 하시는데 도움이 됩니다. 

 링크

SQL Server의 데이터 관리

 

 이전 인덱스의 설명에서 인덱스는 B-트리로 구성된다고 설명 드렸습니다. 

 트리의 노드들은 페이지로 구성되어 있습니다. 

 아래 설명하는 루트 노드는 최상위 노드를 말하고 리프 노드는 최 하위 노드들을 말합니다. 

 인덱스 없는 테이블 

   SQL Server에서 테스트를 위한 테이블을 생성하고 데이터를 삽입합니다. 

-- 테이블 생성 작업
CREATE TABLE TestTbl
(
	UserInitial char(5) NOT NULL,
	Age smallint NOT NULL
);

-- 데이터 삽입 작업
INSERT INTO TestTbl VALUES('TTT',25);
INSERT INTO TestTbl VALUES('SSS',75);
INSERT INTO TestTbl VALUES('AAA',15);
INSERT INTO TestTbl VALUES('RRR',34);
INSERT INTO TestTbl VALUES('QQQ',45);
INSERT INTO TestTbl VALUES('CCC',28);
INSERT INTO TestTbl VALUES('FFF',41);
INSERT INTO TestTbl VALUES('GGG',12);
INSERT INTO TestTbl VALUES('KKK',22);

 

  실제의 데이터들은 어떻게 SQL Server에 기록될까요? 

  아래 그림과 같이 인덱스가 없는 구조에서는 데이터 페이지에 데이터들이 입력된 순서대로 기록됩니다. 

  (구조를 쉽게 이해하기 위해서 페이지당 데이터가 3개씩 들어간다고 가정합니다.)

인덱스가 없는 데이터 구조

 클러스터 인덱스 구조

   클러스터 인덱스 구조에서 인덱스 페이지의 루트 노드 및 중간 노드들은 인덱스 행을 포함하게 구성되어 있습니다. 

   리프 노드들은 기본 테이블의 데이터 페이지로 구성되어 있습니다. 

   기본 테이블 데이터 페이지의 데이터 값들은 인덱스 값을 기준으로 정렬되어 있습니다. 

   인덱스 페이지를 통해서 인덱스를 검색하여 해당하는 데이터 페이지를 찾아가도록 구성되어 있습니다. 

msdn의 클러스터 인덱스 구조

예제를 통한 클러스터 인덱스 설명

 클러스터 인덱스 생성시

위에서 테스트로 생성한 TestTbl 테이블의 "UserInitial" 컬럼에 클러스터 인덱스를 구성하게 되면

 내부구조는 어떻게 변할까요?

클러스터 인덱스 구조

  위와 같이 인덱스 페이지 가 생성되게 됩니다. 

  클러스터 인덱스 페이지의 루트 페이지에는 B-Tree로 정렬된 리프 페이지의 첫번째 "UserInitial" 컬럼의 값과

  페이지 번호로 맵핑됩니다. 

  클러스터 인덱스 페이지의 리프 페이지에는 데이터 페이지로 구성되어 있습니다.

  데이터 페이지의 데이터들은 "UserInitial"열을 기준으로 정렬됩니다. 

 클러스터 인덱스 검색

  TestTbl 테이블에서 FFF 값을 검색한다면 아래와 같이 수행될 것입니다. 

SELECT * FROM TestTbl WHERE UserInitial = 'FFF'

클러스터 인덱스 검색

  첫번째로 인덱스의 루트페이지를 접근해서 찾는 값이 어떤 리프 페이지(데이터 페이지)에 있는지 확인 후 

  리프 페이지로 이동 후에 페이지의 내부 행들을 검색해서 해당 데이터를 찾는 순서로 구성됩니다.

  검색 과정에서 총 2개의 페이지(루트 페이지 + 리프 페이지)를 참조합니다.

 클러스터 인덱스 범위 검색

  TestTbl 테이블에서 FFF에서 QQQ사이의 범위 검색한다면 DB내부에서는 아래와 같이 동작 할 것입니다.

SELECT * FROM TestTbl WHERE UserInitial >= 'FFF' AND UserInitial <= 'QQQ'

 FFF의 페이지를 찾은 다음에 데이터가 정렬되어 있기 때문에 순차적으로 QQQ가 나올 때까지 읽으면 

 검색 데이터를 모두 찾을 수 있습니다. (비 클러스터 인덱스의 경우 정렬되어 있지 않기 때문에 비효율적 아래 설명)

 클러스터 인덱스 삽입

   HHH라는 데이터를 Insert 하게 되면 어떻게 동작할까요?

데이터 삽입1

데이터 삽입2

  데이터 검색과 같이 인덱스를 통해서 삽입 위치를 찾습니다. 만약에 해당 페이지에 공간이 있다면 인덱스 순서에

  맞도록 데이터가 넣어집니다. 하지만 페이지가 가득 차게 될 경우 위의 그림과 같이 페이지 분할 작업이 발생됩니다. 

비클러스터 인덱스 구조

  비클러스터 인덱스또한 클러스터 인덱스 구조와 같이 B-트리 구조를 갖습니다. 

  하지만 클러스터 인덱스와 다른점은 기본 테이블 데이터는 인덱스 값으로 정렬되어 있지 않습니다. 

  클러스터 인덱스와는 다르게 리프노드가 인덱스 페이지로 구성됩니다.

  인덱스 페이지의 값은 클러스터 인덱스와 혼합되어 있는 경우와 아닌 경우에 다르게 구성되어 있습니다.

상  태	비클러스터 인덱스 페이지의 행 데이터
비클러스터 인덱스만	데이터 페이지의 실제 데이터 포인터(데이터 페이지 번호 + 행 번호)
클러스터 인덱스와 혼합	클러스터형의 인덱스 키

msdn 비클러스터 인덱스

예제를 통한 비클러스터 인덱스 설명

 비 클러스터 인덱스 생성시

  TestTbl 테이블의 "UserInitial" 컬럼에 비 클러스터 인덱스를 구성하게 되면 내부구조는 어떻게 변할까요?

  아래와 같이 인덱스 페이지 가 생성되게 됩니다.

  인덱스 페이지의 루트 페이지에는 클러스터와 동일하게 인덱스키와 리프페이지의 페이지 번호로 구성됩니다. 

  하지만 클러스터 인덱스와는 다르게  인덱스 페이지의 리프 페이지는 데이터 페이지가 아닌 데이터 페이지의 포인터로

  구성되어 있습니다.(실제로는 페이지 번호 + 행번호(RID)로 구성됨)

비클러스터 인덱스구조

 비클러스터 인덱스 검색

비클러스터 인덱스 검색

  비클러스터에서 FFF인 데이터를 검색하는 로직을 실행해봅니다.

  첫번째로 인덱스의 루트페이지를 접근해서 찾는 값이 어떤 리프 페이지에 있는지 확인 후

  리프 페이지로 이동 후에 페이지의 내부 행들을 검색해서 데이터의 포인터 정보에 접근합니다. 

  포인터 정보를 기반으로 데이터 페이지에 접근합니다. 

  검색 과정에서 총 3개의 페이지(루트 페이지 + 리프 페이지 + 데이터 페이지)를 참조합니다.

 비클러스터 인덱스 범위 검색 

  비클러스터에서 FFF에서 QQQ 사이의 범위의 데이터를 검색하는 로직을 실행해봅니다.

  클러스터 인덱스의 경우는 데이터가 정렬되어 있기 때문에 FFF만 찾으면 다음 데이터들이 순차적으로 접근이

  가능하지만 비클러스터 인덱스의 경우에는 데이터가 정렬되어 있지 않기 때문에

  검색하려는 범위 데이터 수 * 비클러스터 인덱스 검색 로직의 반복 작업이 필요합니다.

  범위 검색의 크기가 전체 테이블의 5% 이상이 된다면 인덱스를 사용하지 않고

  Table scan 작업이 더 빠르기 때문에 DB 내부에서 자동으로 비 클러스터 인덱스를 사용하지 않도록 

  실행 계획을 세웁니다.

  위와 같이 동작하기 때문에 비클러스터 인덱스에 범위 검색을 사용할 때는 주의해서 사용해야 합니다. 

 비클러스터 인덱스 삽입

비클러스터 인덱스 삽입

비클러스터 인덱스의 삽입은 인덱스의 리프 페이지는 컬럼 순으로 삽입이 되고 실제 데이터 페이지의 데이터는 

삽입 순서대로 추가됩니다.