인덱스가 뭐야 — B-tree 설명

모든 거 밑에 있는 자료구조

인덱스 없으면 모든 WHERE col = ? 가 full table scan: SQLite 가 모든 row 읽고, predicate 체크하고, 매치 반환. O(n). 1000 만 row 면 몇 초, 1 만 row 면 안 보임.

인덱스 = 인덱싱된 컬럼(들) 을 정렬된 순서로 + row 로 가는 포인터로 저장하는 별도 B-tree 자료구조. 인덱스 있으면 WHERE col = ? 가 O(log n) — 테이블 사이즈와 무관하게 page read 몇 번.

SQLite 가 쓰는 B-tree access 3 가지:

Equality — WHERE col = ? 가 매치 키까지 트리 walk.
Range — WHERE col BETWEEN a AND b 가 첫 매치까지 walk 후 forward scan.
Prefix on TEXT — WHERE col LIKE 'pre%' 가 인덱스 사용 (시작 prefix 알려짐); '%suf' 는 못 함.

Principle: 모든 INTEGER PRIMARY KEY 가 이미 인덱스 — SQLite 가 아무 거 안 해도 id 로 즉시 row 찾는 이유. FK 는 자동 인덱싱 안 됨, 직접 인덱스 만들어야 하고 거의 항상 만들어야 해.

Code

인덱스 유무에 따른 query 동작 변화·sql

CREATE TABLE big(id INTEGER PRIMARY KEY, email TEXT, name TEXT) STRICT;

-- 100k row insert (single transaction!)
WITH RECURSIVE cnt(x) AS (SELECT 1 UNION ALL SELECT x+1 FROM cnt WHERE x<100000)
INSERT INTO big(email, name)
SELECT 'user'||x||'@x.com', 'User '||x FROM cnt;

.timer on
SELECT * FROM big WHERE email = 'user99999@x.com';
-- Run Time: real 0.045 user 0.040 ...   (full scan)

CREATE INDEX idx_big_email ON big(email);
SELECT * FROM big WHERE email = 'user99999@x.com';
-- Run Time: real 0.000 user 0.000 ...   (인덱스 사용)

인덱스가 뭐야 — B-tree 설명

모든 거 밑에 있는 자료구조

Code

External links

Exercise

Progress

댓글 0