콘텐츠로 이동

How Tables and Indexes Are Stored on Disk

목차

  1. Table
  2. Row_ID
  3. Page
  4. IO
  5. Heap
  6. Index
  7. 쿼리 예시
  8. Notes

Table

논리적 테이블은 행(row)과 열(column)으로 구성된다.

emp_id emp_name emp_dob 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

  • 내부적으로 시스템이 관리하는 식별자
  • MySQL (InnoDB): row_id가 Primary Key와 동일
  • Postgres: 별도의 시스템 컬럼 row_id (tuple_id)를 가짐
row_id emp_id emp_name emp_dob 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

Page

  • 저장 모델(row vs column store)에 따라 행들은 논리적 페이지(Page) 단위로 저장되고 읽힌다
  • 데이터베이스는 단일 행을 읽지 않는다 - 한 번의 IO로 페이지 단위(또는 그 이상) 를 읽고, 그 안의 많은 행을 가져온다
  • 각 페이지는 고정 크기를 가진다:
  • Postgres: 8KB
  • MySQL: 16KB

예시

페이지당 3개의 행을 저장한다고 가정하면, 1001개의 행이 있을 때:

1001 / 3 = 약 333개 페이지

┌─────────────────────────────────────┐
│ Page 0                              │
│ 1,10,Hussein,1/2/1988,$100,000      │
│ 2,20,Adam,3/2/1977,$200,000         │
│ 3,30,Ali,5/2/1982,$300,000          │
├─────────────────────────────────────┤
│ Page 1                              │
│ (Rows 4, 5, 6) ...                  │
├─────────────────────────────────────┤
│ Page 2                              │
│ (Rows 7, 8, 9) ...                  │
├─────────────────────────────────────┤
│ .......                             │
├─────────────────────────────────────┤
│ Page 333                            │
│ ...1000,10000,Eddard,1/27/1999,...  │
└─────────────────────────────────────┘

IO

  • IO (Input/Output): 디스크에 대한 읽기 요청
  • IO를 최소화하는 것이 핵심 - IO는 비용이 비싸다
  • 한 번의 IO로 1개 이상의 페이지를 가져올 수 있다 (디스크 파티션 등에 따라 다름)
  • IO는 단일 행을 읽을 수 없다 - 페이지 단위로 읽으며, 같은 페이지의 다른 행들은 "공짜"로 얻게 된다
  • 일부 IO는 OS 캐시에서 처리되어 실제 디스크까지 가지 않을 수 있다

Heap

  • Heap은 테이블의 모든 페이지가 순차적으로 저장된 데이터 구조
  • 실제 데이터가 저장되는 곳 (모든 컬럼의 모든 데이터 포함)
  • Heap을 전체 탐색하는 것은 비용이 크다 → 원하는 것을 찾기 위해 많은 데이터를 읽어야 함
  • 그래서 인덱스가 필요하다 - Heap의 어느 페이지를 읽어야 하는지 정확히 알려줌

Index

  • 인덱스는 Heap과 별도의 데이터 구조로, Heap에 대한 "포인터"를 가짐
  • 데이터의 일부만 가지고 빠른 검색에 사용됨
  • 하나 이상의 컬럼에 대해 인덱스를 생성할 수 있음
  • 인덱스에서 값을 찾으면, Heap으로 가서 나머지 정보를 가져옴
  • 인덱스는 Heap의 정확한 페이지를 알려줌 → 모든 페이지를 스캔하는 비용을 절약
  • 인덱스도 페이지로 저장되며, 인덱스 항목을 가져오는 데에도 IO가 필요
  • 인덱스가 작을수록 메모리에 더 많이 적재 가능 → 검색이 더 빠름
  • 인덱스에 많이 사용되는 자료구조는 B-Tree

인덱스 구조 예시 (EMP_ID 인덱스)

Index on EMP_ID                           Heap
┌─────────────────────────────┐           ┌─────────────────────┐
│ Page 0                      │           │ Page 0              │
│ 10 (1,0) | 20 (2,0) | 30 (3,0)│  ──→   │ Rows 1,2,3          │
│ 40 (4,1) | 50 (5,1) | 60 (6,1)│        ├─────────────────────┤
│ 70 (7,2) | 80 (8,2) | 90 (9,2)│        │ Page 1              │
├─────────────────────────────┤           │ Rows 4,5,6          │
│ Page 1                      │           ├─────────────────────┤
│ 100(10,3)|110(11,3)|120(12,3)│          │ Page 2              │
│ 130(13,4)|140(14,4)|150(15,4)│          │ Rows 7,8,9          │
│ 160(16,5)|170(17,5)|180(18,5)│          ├─────────────────────┤
├─────────────────────────────┤           │ .......             │
│ .....                       │           ├─────────────────────┤
├─────────────────────────────┤           │ Page 333            │
│ Page N                      │           │ ...row 1000...      │
│ 9920(992,331)|9930(993,331) │           └─────────────────────┘
│ ...                         │
│ 10000(1000,333)             │
└─────────────────────────────┘
  • 인덱스 항목 형식: EMP_ID (row_id, page_number)
  • IO1: 인덱스에서 page/row를 찾기
  • IO2: Heap에서 해당 페이지를 가져오기

쿼리 예시

인덱스 없이 (Full Table Scan)

SELECT * FROM EMP WHERE EMP_ID = 10000;
  • Heap의 모든 페이지를 처음부터 끝까지 순차적으로 스캔
  • Page 0 → Page 1 → Page 2 → ... → Page 333
  • 333번의 IO 필요 (최악의 경우)

인덱스 있을 때 (Index Scan)

SELECT * FROM EMP WHERE EMP_ID = 10000;
  1. 인덱스에서 10000 검색 → 10000 (1000, 333) 발견
  2. Heap의 Page 333만 읽어서 row 1000을 가져옴
  3. 단 2번의 IO (인덱스 1번 + Heap 1번)

Notes

  • 때때로 Heap 테이블이 단일 인덱스를 기준으로 정렬될 수 있다 → Clustered Index 또는 Index Organized Table (IOT)
  • Primary Key는 일반적으로 Clustered Index이다 (달리 명시하지 않는 한)
  • MySQL InnoDB: 항상 Primary Key (Clustered Index)를 가짐. 다른 인덱스들은 Primary Key "값"을 가리킴
  • Postgres: Secondary Index만 존재. 모든 인덱스가 Heap에 있는 row_id를 직접 가리킴
DBMS 인덱스 방식
MySQL (InnoDB) Primary Key = Clustered Index, Secondary Index → PK 값을 가리킴
Postgres 모든 인덱스가 row_id (tuple_id)를 직접 가리킴