DB 테이블과 인덱스가 디스크에 저장되는 방법

 

데이터베이스의 테이블과 인덱스가 디스크에 어떻게 저장이 되고 그리고 SELECT를 했을 때 어떤 식으로 데이터를 가져오는지 정리해보려고 한다!

 

Table 

데이터베이스에서 테이블은 저장소에 비트와 바이트 형태로 저장한다.

가로: row(행), 세로: column(열)

emp_id	emp_name	emp_birth	emp_salary
2000	Hussein	1/2/1988	$100,000
3000	Adam	3/2/1977	$200,000
4000	Ali	5/2/1982	$300,000

 

Row_ID

1. 사용자가 직접 생성하거나 수정할 수 없는 내부 시스템에 의해 관리되는 열이다.

2. 데이터베이스 관리 시스템이 내부적으로 사용하고 유지 관리하는 식별자로, 각 행을 고유하게 식별하는 데 사용된다.

row_id	emp_id	emp_name	emp_birth	emp_salary
1	2000	Hussein	1/2/1988	$100,000
2	3000	Adam	3/2/1977	$200,000
3	4000	Ali	5/2/1982	$300,000

데이터베이스 시스템마다 Row_ID의 구현과 사용 방식이 다르다.

MySQL의 InnoDB 스토리지 엔진: Row_ID는 주 키와 같은 역할을 할 수 있고 주 키가 명시적으로 정의되지 않은 경우, InnoDB는 내부적으로 Row_ID를 사용하여 각 행을 식별할 수 있다.
PostgreSQL: Row_ID는 특별한 시스템 열로 tuple_id 또는 ctid라고도 불립니다. 이 열은 행의 물리적 위치를 나타내며, 각 행이 데이터베이스 파일 내에서 어디에 저장되어 있는지를 나타내는 포인터 역할을 한다.

 

Page

1. 스토리지 모델(행 저장소 vs 열 저장소)에 따라 행은 논리적 페이지로 저장되고 읽힌다. 
2. 데이터베이스는 단일 행을 읽는 것이 아니라 단일 IO에서 한 페이지 이상을 읽으며 해당 IO에서 많은 행을 얻는다.
3. 각 페이지에는 크기가 있다(예: postgres의 경우 8KB, MySQL의 경우 16KB)

4. IO를 수행하면 한 페이지 또는 두 페이지 이상을 가져오는데 디스크 파티션에 따라 다르다.

row_id	emp_id	emp_name	emp_birth	emp_salary
1	2000	Hussein	1/2/1988	$100,000
2	3000	Adam	3/2/1977	$200,000
3	4000	Ali	5/2/1982	$300,000
...	...	...	...	...
1000	10000	Eddard	1/27/1999	$250,000

 

위 테이블이 만약 각 페이지에 3행씩 저장되었다고 가정하면, 1001행이 있으니 1001/3 = 약 333 페이지가 된다.

Page 0	Page 1	...	Page 333
1 2000 Hussein 1/2/1988 $100,000, 2 3000 Adam 3/2/1977 $200,000, 3 4000 Ali 5/2/1982 $300,000,	Row 4, 5, 6		More ... 1000 10000 Eddard 1/27/1999 $250,000

 

IO(입력/출력)

1. IO는 디스크에 대한 읽기 요청이다.
2. IO는 비용이 많이 들기 때문에 가능한 한 이를 최소화하려고 노력한다 => 적을수록 쿼리가 빨라진다.
3. IO는 디스크 파티션 및 기타 요인에 따라 1페이지 이상을 가져올 수 있다. 
4. IO는 단일 행을 읽을 수 없으며, 많은 행이 포함된 페이지를 가져온다. 
5. 운영 체제의 일부 IO는 디스크가 아닌 운영 체제 캐시로 이동한다. => 특히 Posatgres의 경우에 해당

 

Heap

1. 힙은 데이터베이스에서 테이블이 저장되는 주요한 데이터 구조 중 하나이다.

2. 힙 구조에서 각 페이지는 테이블 내의 데이터 블록을 나타내며, 이들 페이지가 모여 전체 테이블을 구성한다.

3. 데이터베이스는 이런 페이지들을 통해 테이블의 데이터를 물리적으로 저장하고 관리한다.

4. 주로 데이터를 순서에 상관없이 추가할 때 사용되며, 데이터는 페이지에 순차적으로 채워진다.
5. 테이블의 모든 데이터가 포함되어 있으며, 모든 세부 정보와 데이터 필드가 포함된다.
6. 원하는 것을 찾기 위해 수많은 데이터를 읽어야 하므로 힙을 탐색하는 데는 많은 비용이 든다.
7. 그렇기 때문에 힙의 어느 부분을 읽어야 하는지 정확히 알려주는 인덱스가 필요하다.

 

Index

1. 인덱스는 힙과 별도로 힙에 대한 '포인터'(Row_ID와 행을 가리키는 숫자)를 가진 또 다른 데이터 구조이다.
2. 데이터의 일부를 가지고 있으며 무언가를 빠르게 검색하는 데 사용된다.
3. 한 열 이상에서 인덱싱을 할 수 있다.
4. 인덱스는 힙의 모든 페이지를 스캔하는 대신 힙에서 어떤 페이지를 가져올지 정확히 알려준다.
5. 인덱스 또한 페이지로 저장되며 인덱스의 항목을 가져오는 데 IO 비용이 발생한다.
6. 인덱스가 작을수록 메모리에 더 많이 들어갈 수 있으므로 검색 속도가 빨라진다.
7. 인덱스에 널리 사용되는 데이터 구조는 b-tree이다.

 

Index로 저장되었을 때 예시(emp_id)

emp_id(Row_id, Page N)

Page 0	Page 1	...	Page N
10(1,0), 20(2,0), 30(3,0) 40(4,1), 50(5,1), 60(6,1) ...	100(10,3), 110(11,3), 120(12,3) 130(13,4), 140(14,4), 150(15,4) ...		... 9950(995,332), 9960(996,332), 9970(997,332) 9980(998,333), 9990(999,333), 10000(1000,333)

 

추가 내용

1. 때로는 힙 테이블을 단일 인덱스를 중심으로 구성할 수 있는데, 이를 클러스터 된 인덱스 또는 인덱스 구성 테이블이라고 한다.
2. 기본 키는 달리 명시되지 않는 한 일반적으로 클러스터 된 인덱스이다. 
3. MySQL InnoDB에는 항상 기본 키(클러스터 된 인덱스)가 있으며 다른 인덱스는 기본 키 "값"을 가리킨다. 
4. Postgres에는 보조 인덱스만 있으며 모든 인덱스는 힙에 있는 row_id를 직접 가리킨다.

 

최종 정리(+ 쿼리 과정 포함)

 데이터베이스에서는 각 행이 비트와 바이트 형태로 구성된 페이지에 저장되어, 디스크에 위치한 힙 구조를 형성하고 물리적으로 디스크에 저장된다. 사용자의 SELECT 쿼리가 실행될 때 WHERE 절 등의 조건에 의해 필터링된 Row_ID를 식별하여 해당하는 특정 페이지를 힙에서 검색한다. 페이지에서 필요한 행 데이터를 추출하여 사용자에게 결과를 반환한다.

 이 모든 데이터 액세스 과정에서 I/O 작업이 발생하는데, I/O는 디스크와 메모리 간의 데이터 이동을 포함하므로 시간과 자원을 소모한다. 그렇기에 I/O 과정을 최소화하고 성능을 향상하기 위해 인덱스를 사용한다. 이때 인덱스를 사용하게 되면 힙 전체를 검색하지 않고도 특정 페이지를 직접 찾을 수 있으며, 이는 I/O 작업을 크게 줄이고 쿼리 성능을 향상한다.