Search

테이블과 인덱스 구조

본 글은, 오프라인 강의인 StartUP Tuning For PostgreSQL을 책으로 펼치기 위해 정리 중인 글입니다.
지난 글(link iconINDEX 개념잡기INDEX 개념잡기)에 이어서, 테이블과 인덱스의 물리적인 구조에 대해 살펴봅니다. PostgreSQL에서 테이블은 Heap 구조로, 인덱스는 일반적으로 B Tree 구조로 구성된다. Heap과 B Tree 모두, I/O의 최소 단위인 블록(Block, 또는 페이지(Page)라는 용어를 사용한다.)이 모여서 만들어지는 구조다.

테이블 구조

관계형 데이터베이스에서 대표적으로 사용하는 테이블 구조는 Heap 또는 Clustered다. Heap 구조는 별도의 정렬 기준 없이 데이터를 저장하는 구조다. Heap 구조는 데이터를 블록 단위로 나누어서 저장한다. 앞으로 설명의 편의를 위해 데이터가 저장된 블록은 ‘데이터 블록’이라고 부른다. 데이터 블록이 일정한 순서 없어 모여서 Heap 구조가 만들어진다. 물론, 데이터 블록 내에서도 레코드의 순서는 무작위다. 간단하게 Heap 구조를 표현해 보면, 아래 그림과 같다. 아래는 총 4개의 블록이 모여 있는 Heap 구조다. 블록별로 세 건의 레코드가 저장되어 있다. 실제 PostgreSQL은 한 블록에 8KB의 공간을 할당하므로 8KB만큼의 레코드가 채워진다.
Clustered 구조는 정해진 정렬 기준에 따라 데이터를 저장하는 테이블 구조다. 클러스터드 구조 역시 블록 단위로 데이터를 저장한다. 블록 내에 데이터는 정해진 기준에 따라 정렬되어 있으며, 블록들도 같은 기준으로 정렬된 상태다. ord_no 컬럼 기준으로 정렬된 Clustered 구조를 간단히 그려보면 아래와 같다. 거래처ID에 따라 레코드와 블록이 정렬되어 있다. 아래 그림에서는 데이터가 입력된 데이터 블록만 표시되어 있다. Clustered 구조처럼 데이터의 정렬을 유지하려면, 아래 그림의 데이터 블록 외에도, 정렬을 유지하기 위한 추가적인 블록들이 필요하다. 이러한 블록들이 모두 모이면 실제로는 B Tree와 같은 구조가 된다. B Tree는 인덱스를 위한 구조이기 때문에, Clustered를 Clustered Index라고 부르기도 한다.

Heap VS. Clustered

관계형 데이터베이스는 Heap 또는 Clustered 구조를 대표적으로 사용해 테이블의 데이터를 관리한다. (이외에도 다른 방식이 존재한다.) ORACLE과 PostgreSQL은 기본적으로 Heap 구조로 테이블을 생성한다. PostgreSQL은 Heap 구조만 지원하며, ORACLE은 Heap 구조와 함께 IOT(Index-Organized Table) 구조도 지원한다. IOT가 바로 여기서 설명한 Clustered 구조다. MySQL과 MariaDB의 InnoDB는 테이블을 무조건 Clustered 구조로만 관리한다.
하나의 테이블이 동시에 두 가지 구조를 가질 수는 없다. 하나의 테이블은 Heap 또는 Clustered, 둘 중에 하나의 구조로만 생성할 수 있다.
PostrgreSQL의 CLUSTER 이 명령어는 저장된 데이터를 일회성으로 정렬 처리할 뿐, 영구적인 데이터 정렬 순서를 보장해주지는 않는다. CLUSTER 명령어는 테이블 전체에 LOCK을 걸 수 있으므로, 함부로 사용해서는 안된다. (버젼에 따라 다를 수 있다.)

인덱스 구조

관계형 데이터베이스에서 인덱스는 일반적으로 B-Tree 자료구조로 만들어진다. 나무(Tree)가 뿌리(Root)와 가지(Branch), 잎(Leaf)으로 구성된 것처럼, B-Tree 구조 역시 뿌리, 가지, 잎이라는 세 계층으로 구성된다. B-Tree 구조를 그림으로 표현할 때는 뿌리를 가장 위에, 잎을 가장 아래에 표현한다. 마치 나무를 뒤집어 놓은 것처럼 말이다. 아래 그림은 거래처 이름으로 구성한 B-Tree 인덱스 구조다.
데이터 블록이 모여 Heap이 구성된 것처럼, B Tree 역시 블록이 모여 만들어진다. 앞으로, 인덱스를 구성하는 블록은 ‘인덱스 블록’이라 부른다. B-Tree를 구성하는 계층인 루트(Root, 뿌리), 브랜치(Branch, 가지), 리프(Leaf, 잎) 각각은 계층에 따라 하나 또는 여러 개의 블록으로 구성되어 있다. 각 계층의 특징은 다음과 같다.
•
루트(Root): B-tree 구조에서 탐색을 시작하는 계층으로 단 하나의 블록으로 되어 있다.
•
브랜치(Branch): 루트에서 리프로 거쳐가는 중간 계층이다. Middle 계층으로 부르기도 한다.
◦
하나의 브랜치 계층에는 여러 블록이 존재할 수 있다.
◦
그림에서는 브랜치가 하나의 계층으로 되어 있지만, 두 개 이상의 계층을 가질 수도 있다.
•
리프(Leaf): B-tree 구조의 가장 하위에 존재하는 계층이다.
◦
인덱스를 이용해 찾으려고 하는 실제 값이 저장되는 블록이다.
◦
오직, 단 하나의 층만 존재하며, 여러 개의 블록으로 구성되어 있다.
◦
리프에는 인덱스 키로 지정한 모든 데이터의 값이 저장되어 있다.
▪
이와 함께 해당 키가 속한 실제 레코드의 물리적인 주소(ctid)가 포함되어 있다.
◦
리프에 저장된 값들은 항상 정렬된 상태다.
◦
리프는 근접한 리프와 서로 연결되어 있다.
▪
정렬된 데이터를 순서대로 탐색하기 위해서 연결된 정보를 활용한다.
B-Tree의 리프에는 실제 찾아야 하는 값이 모두 들어 있다. 리프에 저장된 값을 가장 빠르게 찾아가는 길은 루트에서 출발해 브랜치(중간)를 거쳐 리프에 도달하는 것이다.
‘B-Tree’의 ‘B’는 Balanced(균형 잡힌)를 뜻한다. 균형이 잡혔다는 말은, 리프에 저장된 어떤 값을 찾더라도 루트에서 리프까지 탐색하는 블록의 수가 항상 같다는 의미다. 다시 말해 모든 경로가 동일한 깊이(루트에서 리프까지)가 유지되므로 탐색 시간도 일정하게 보장된다.
지금까지 설명한 내용의 핵심을 간단히 정리하면 다음과 같다.
•
테이블 구조: Heap 또는 Clustered
◦
Heap: 특별한 정렬 기준 없이 데이터를 저장하는 구조
◦
Clustered: 정해진 기준에 따라 데이터를 정렬해 저장하는 구조
•
인덱스 구조: B Tree 구조
◦
루트, 브랜치, 리프로 구성되어 있다.
◦
루트는 검색을 시작하는 계층으로 단 하나의 블록으로 구성된다.
◦
브랜치는 루트에서 리프를 찾아가기 위한 중간 계층으로 여러 층으로 구성될 수 있다.
▪
브랜치는 한 층에 여러 블록이 존재할 수 있다.
◦
리프는 인덱스 컬럼의 모든 값이 저장된 계층이다.
▪
한 층으로만 이루어지며, 여러 블록이 존재할 수 있다.
▪
근접한 리프는 서로 연결되어 있다.
◦
루트에서 시작해 브랜치를 거쳐 리프에 저장된 값을 찾는다면,
▪
어떤 값을 찾든, 동일한 양의 블록에 접근한다. (동일한 검색 속도를 보장한다.)
•
테이블을 구성하는 블록을 데이터 블록, 인덱스를 구성하는 블록을 인덱스 블록이라고 부르자.
준비한 내용은 여기까지입니다.
데이터 활용이 필요한 모든 분을 위한 SQL 실무서를 소개합니다.
•
SQL 입문자를 위한 실습환경 구성과 SELECT 기초부터
•
SQL 중급자를 위한 GROUP BY와 JOIN, 그리고 분석함수까지!
•
그림과 친절한 설명, 손끝으로 익히는 실습 SQL과 실무형 퀴즈를 더한 올인원 SQL 실무서