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

전부의 밑을 받치는 자료구조

인덱스가 없으면 WHERE col = ?은 전부 full table scan이야. SQLite가 row를 하나씩 다 읽고 조건을 검사해서 걸리는 걸 돌려주지. O(n)이야. row가 1000만이면 몇 초가 걸리고, 1만이면 눈에도 안 띄어.

인덱스는 인덱싱한 컬럼을 정렬된 순서로 담고 원래 row로 가는 포인터를 붙여둔 별도의 B-tree야. 인덱스가 있으면 WHERE col = ?이 O(log n)이 돼. 테이블이 아무리 커져도 page를 몇 번만 읽으면 끝나.

SQLite가 B-tree를 타는 방식은 셋이야.

Equality — WHERE col = ?이면 맞는 키까지 트리를 타고 내려가.
Range — WHERE col BETWEEN a AND b면 첫 지점까지 내려간 다음 거기서부터 쭉 훑어.
TEXT의 앞부분 매치 — WHERE col LIKE 'pre%'는 시작이 정해져 있으니 인덱스를 타. '%suf'는 못 타고.

Principle: INTEGER PRIMARY KEY는 그 자체로 이미 인덱스야. 아무것도 안 했는데 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