Tag: B-tree

이 태그가 달린 글들 "B-tree"

• RDB Mastery #2 — MySQL 인덱스의 종류: B-tree / Hash / Covering / Composite / Multi-valued / Functional, 그리고 언제 무엇을 고를 것인가

  4 May, 2026

  InnoDB 의 모든 인덱스가 B-tree 가 아닙니다. Hash (Memory engine), Spatial (R-tree), Full-text (역인덱스), Multi-valued (8.0+, JSON 배열), Functional (8.0.13+, 표현식). 그리고 같은 B-tree 안에서도 clustered vs secondary, covering 여부, composite 의 leftmost prefix, cardinality / selectivity 가 결정의 축이 됩니다. 1,000만 row 환경에서 5종 인덱스를 직접 만들어 cardinality + Q1~Q5 latency 변화로 언제 무엇을 고를지를 측정으로 결정. Q3 covering 2,476배 / Q5 composite 577배 / Q2 역설 (인덱스 추가가 느려지는 케이스 0.66ms → 13.5ms). 인덱스는 공짜가 아닙니다 — 쓰기 비용 5~6배 + storage 1.3GB. 9개 다이어그램으로 끝까지 풀어봅니다.

• RDB Mastery #1 — InnoDB 인덱스 내부 구조: No-Index 부터 다중 인덱스까지 B-tree 가 그리는 진짜 그림

  4 May, 2026

  인덱스를 안 걸어도 InnoDB 안에서는 이미 B-tree 입니다. PK 가 clustered index = 테이블 자체. Secondary index 는 PK 를 가리키는 별도 B-tree. Covering index 는 PK 까지 안 가도 답이 있는 인덱스. Reverse scan 은 leaf 의 양방향 linked list 를 거꾸로 walk. OFFSET 이 건너뛸 수 없는 이유는 B-tree 가 row 카운터를 안 가지기 때문. Cursor 가 빠른 이유는 WHERE 가 binary search primitive 를 트리거하기 때문. 다중 인덱스 = 같은 테이블에 N 개 B-tree. 1,000만 row 환경에서 [실측] Q3 covering 2,476배 / Q5 composite 577배 / OFFSET 1M 171ms / cursor 0.30ms — 다이어그램 10개로 끝까지 풀어봤습니다.