SQL Server 인덱스 내부 구조 심층 분석

인덱스 설계는 데이터베이스 성능에 결정적인 영향을 미치는 중요한 요소입니다. 그러나 적절한 인덱스를 설계하는 것은 쉽지 않으며, 많은 개발자들이 부적절한 인덱스 생성으로 인해 오히려 성능 저하를 경험하기도 합니다. 이처럼 인덱스는 데이터베이스 성능에 있어 양날의 검과 같습니다.

이전 글에서는 인덱스의 논리적 구조와 개념적 측면에 대해 다루었습니다. 이제부터는 인덱스의 물리적 구조에 대해 살펴보겠습니다. 인덱스의 내부 구조와 SQL Server가 이를 어떻게 관리하는지 이해하는 것은 데이터 조작(삽입, 삭제, 수정) 및 인덱스 관리 작업이 발생시키는 비용을 이해하는 데 필수적입니다.

리프 레벨과 비리프 레벨

모든 인덱스는 리프(leaf) 레벨과 비리프(non-leaf) 레벨로 구성됩니다. 이전 글에서는 주로 인덱스의 리프 레벨에 초점을 맞췄습니다. 클러스터형 인덱스의 경우 리프 노드가 인덱스 자체이며, 각 리프 노드에 포함된 항목은 테이블의 실제 행입니다. 비클러스터형 인덱스의 경우 각 리프 노드는 인덱스 키 열, 선택적 포함 열(included column) 및 북마크(클러스터형 인덱스 키 또는 RID)로 구성된 항목을 포함합니다.

인덱스 항목은 테이블 행에서 오는 것(클러스터형 인덱스 리프 노드), 테이블 행을 가리키는 것(비클러스터형 인덱스 리프 노드) 또는 하위 레벨 노드를 가리키는 것(비리프 노드)에 관계없이 인덱스 행이라고 할 수 있습니다.

비리프 노드는 리프 노드 레벨의 상위 레벨로, SQL Server는 비리프 노드를 다음과 같은 목적으로 사용합니다:

인덱스 키에 따라 인덱스를 정렬된 상태로 유지
인덱스 키를 기반으로 리프 노드를 빠르게 찾기

이 시리즈의 첫 번째 글에서는 전화번호부 비유를 통해 인덱스가 성능을 향상시키는 이유를 설명했습니다. 사용자는 전화번호부가 성으로 정렬되어 있다는 것을 알기 때문에 "Meyer, Helen"을 찾을 때 M으로 시작하는 이름이 대략 전화번호부 중간에 위치한다는 것을 알고 바로 해당 부분부터 검색을 시작할 수 있습니다. 하지만 SQL Server는 알파벳 순서나 어떤 페이지가 중간 페이지인지 알지 못하며, 인덱스의 모든 페이지를 스캔하지 않고는 특정 항목을 찾을 수 없습니다. 모든 페이지를 스캔하지 않고 필요한 항목을 찾기 위해 SQL Server는 리프 노드 위에 추가적인 페이지를 구축합니다.

비리프 레벨

이러한 추가적인 페이지를 비리프 노드 또는 인덱스의 노드 레벨이라고 하며, 리프 레벨 위에 구축됩니다. 비리프 레벨의 목적은 SQL Server가 특정 인덱스를 검색할 때 통합된 진입점 페이지를 가지게 하고 모든 페이지를 스캔할 필요가 없게 하는 것입니다.

인덱스의 모든 페이지는 어떤 레벨에 속하든지 인덱스 항목을 포함합니다. 앞서 반복해서 언급했듯이, 클러스터형 인덱스의 경우 리프 노드의 항목이 실제 행을 포함하므로, 테이블에 10억 행이 있다면 리프 노드에는 10억 개의 항목이 포함됩니다.

리프 노드 위의 레벨, 즉 비리프 노드의 가장 하위 레벨에서는 각 인덱스 항목이 리프 노드를 가리킵니다. 테이블의 각 페이지가 100개의 항목을 수용할 수 있다면, 10억 행은 1000000000/100=1000만 개의 페이지가 필요하며, 따라서 가장 하위 비리프 노드에는 1000만 개의 항목이 포함되어 1000만/100=10만 개의 페이지에 분산됩니다.

그 다음 상위 비리프 노드 레벨은 이 10만 개의 페이지를 가리키는 항목, 즉 10만 개의 항목을 포함하며, 이 10만 개의 인덱스 항목은 10만/100=1000개의 페이지에 분산됩니다. 이 패턴에 따라 그 다음 상위 레벨은 10개의 페이지를 포함하며, 최상위 노드는 단 하나의 페이지만 갖게 됩니다.

인덱스의 최상위 노드를 루트 페이지(root page)라고 합니다. 루트 페이지와 리프 노드를 제외한 나머지 레벨을 중간 레벨(intermediate level)이라고 합니다. 레벨 번호는 리프 노드를 0으로 시작하여 상위로 갈수록 증가하므로, 중간 레벨은 1부터 시작합니다.

비리프 노드는 인덱스 키만 포함하며, 포함 열을 가진 인덱스의 경우 포함 열은 리프 노드에만 존재합니다.

인덱스의 페이지는 루트 페이지를 제외하고 모두 인덱스 순서에 따라 현재 페이지의 이전과 다음 페이지를 가리키는 두 개의 추가 포인터를 가집니다. 이러한 양방향 연결 리스트 구조는 SQL Server가 인덱스 스캔을 수행할 때 더 효율적이게 합니다.

간단한 예제

인덱스의 내부 구조를 실제로 이해하기 위해 간단한 도표를 살펴보겠습니다. Personnel.Employee 테이블에 다음과 같이 비클러스터형 인덱스를 생성합니다:

CREATE NONCLUSTERED INDEX IX_Employee_Name 
ON Personnel.Employee (LastName, FirstName)
GO

도표 설명:

페이지를 가리키는 포인터는 파일 번호와 페이지 번호를 포함합니다. 예를 들어 5:4567은 5번 파일의 4567번 페이지를 가리킵니다.

위 도표는 단지 예시일 뿐이며, 실제로는 각 페이지에 훨씬 더 많은 행이 포함되고 페이지 수도 훨씬 더 많습니다.

실제 페이지에서 인덱스 항목은 정렬되어 저장되지 않으며, 페이지 끝의 오프셋 테이블을 통해 위치가 결정됩니다. 이 오프셋 테이블은 정렬되어 있습니다.

대부분의 경우 페이지는 도표에 표시된 것처럼 물리적으로 연속되지 않지만, 논리적으로는 연결되어 있습니다. 이러한 논리적 구조와 물리적 구조 간의 차이를 단편화(fragmentation)라고 합니다.

앞서 언급했듯이, 각 인덱스는 하나 이상의 중간 페이지 레벨을 가질 수 있습니다.

다시 전화번호부 비유를 사용해 보겠습니다. "Helen Meyer"라는 연락처를 찾는 경우, 전화번호부의 첫 페이지를 열고 "Fernandez, Zelda"와 "Olsen, Karl" 사이의 이름은 페이지 5:431을 참조하라는 안내를 찾습니다. 그런 다음 431 페이지로 가면 "Kumar, Kevin"과 "Nara, Alison" 사이의 이름은 페이지 5:2006을 참조하라는 안내를 찾을 수 있습니다. 마지막으로 5:2006 페이지로 가면 원하는 연락처를 찾을 수 있습니다.

인덱스 깊이

인덱스의 루트 페이지 및 관련 정보는 시스템 테이블에 저장됩니다. SQL Server가 페이지 검색을 수행할 때마다 루트 페이지에서 시작하여 중간 노드를 거쳐 리프 노드에 도달한 후, 리프에서 필요한 인덱스 항목을 찾습니다. 10억 행이 있는 테이블의 경우 루트 노드에서 리프 노드까지 총 5레벨을 읽어야 합니다. 반면 앞서 도표에 표시된 노드의 경우 3번의 IO만으로 충분합니다.

이러한 레벨 수를 인덱스 깊이(index depth)라고 하며, 인덱스 키의 크기와 수에 따라 달라집니다. AdventureWorks 예제 데이터베이스에서는 3레벨을 초과하는 인덱스가 없지만, 인덱스 키가 넓거나 데이터량이 많은 테이블에서는 더 깊은 레벨을 가질 수 있습니다.

sys.dm_db_index_physical_stats 함수는 인덱스의 상세 정보, 깊이 및 크기를 보여줍니다. 이 함수는 테이블 반환 함수이며, 다음 코드를 사용하여 SalesOrderDetail 테이블의 인덱스 정보를 확인할 수 있습니다.

SELECT 
    OBJECT_NAME(stats.object_id) AS 'TableName',
    idx.name AS 'IndexName',
    stats.index_id AS 'IndexID',
    stats.index_type_desc,
    stats.index_depth,
    stats.page_count
FROM 
    sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), NULL, NULL, 'LIMITED') stats
JOIN 
    sys.indexes idx ON idx.object_id = stats.object_id AND idx.index_id = stats.index_id;

다음 코드를 사용하면 더 상세한 레벨 정보를 볼 수 있습니다.

SELECT 
    OBJECT_NAME(stats.object_id) AS 'TableName',
    idx.name AS 'IndexName',
    stats.index_id AS 'IndexID',
    stats.index_type_desc,
    stats.index_level,
    stats.page_count
FROM 
    sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), NULL, NULL, 'DETAILED') stats
JOIN 
    sys.indexes idx ON idx.object_id = stats.object_id AND idx.index_id = stats.index_id
ORDER BY 
    stats.index_level DESC;

결과를 통해 다음 사항을 알 수 있습니다:

리프 노드 항목은 407개 페이지에 분산
중간 노드는 단 2개 페이지만 필요
루트 노드는 1개 페이지만 존재

인덱스 키 선택과 북마크 크기에 따라 리프 노드는 일반적으로 비리프 노드보다 수백 배 더 큽니다. 이는 실제 데이터에 따라 달라집니다.

포함 열은 비클러스터형 인덱스에만 적용되며 리프 노드에만 존재한다는 점을 기억하세요. 포함 열은 상위 레벨에서는 투명하므로 비리프 노드 키 크기를 증가시키지 않습니다.

클러스터형 인덱스의 리프 노드는 테이블 데이터 자체이므로, 리프 노드의 데이터가 테이블 데이터인 것 외에도 추가적인 비리프 레벨을 저장하기 위한 공간이 필요합니다. 클러스터형 인덱스 생성 시 데이터 자체는 이미 존재하므로, 인덱스 생성에는 시간과 리소스가 소요될 뿐만 아니라 생성 후에는 비리프 노드를 저장하기 위한 추가 공간도 필요합니다.

인덱스 구조를 통해 SQL Server는 키 값을 기반으로 필요한 열을 빠르게 찾을 수 있습니다. 일단 필요한 열을 찾으면 SQL Server는 다음 작업을 수행할 수 있습니다:

필요한 행에 직접 접근
찾은 데이터 위치부터 시작하여 양방향 연결 리스트를 따라 인접한 페이지 찾기

인덱스 트리 구조는 관계형 데이터베이스가 등장하기 전부터 사용되어 왔으며, 효율적인 데이터 검색을 위한 뛰어난 구조로 입증되었습니다.

태그: SQL Server 인덱스 데이터베이스 성능 클러스터형 인덱스 비클러스터형 인덱스

8월 3일 15:57에 게시됨

괴물 클럽

SQL Server 인덱스 내부 구조 심층 분석

리프 레벨과 비리프 레벨

비리프 레벨

간단한 예제

인덱스 깊이

인기 태그