← Notedeck
All engines
·
数据库
en
zh-CN
zh-TW
ja
ko
fr
de
es
pt-BR
tr
it
ar
数据库
12
engines
B-tree index · split & search
B-tree index · split & search
order m · 溢出分裂上推中位 · 查找路径高亮
Sorted, balanced multi-way tree; overflowing nodes split and push the median up
B+ tree · leaf chain & range scan
B+ tree · leaf chain & range scan
值全在叶 · 叶链表 · 范围扫描走叶链
All data lives in linked leaves; internal nodes are separators only
Extendible hashing · directory & buckets
Extendible hashing · directory & buckets
目录全局深度/桶局部深度 · 桶分裂 · 目录翻倍
Index by the low bits of the hash; overflow splits a bucket, and doubles the directory when needed
Nested-loop join
Nested-loop join
外×内逐元组 · 比较数|R|·|S| · vs匹配
For each R tuple, scan all of S · O(|R|·|S|) comparisons
Hash join
Hash join
build建哈希表 · probe探测 · 分区
Build a hash table on the smaller relation, then probe · near-linear
Sort-merge join
Sort-merge join
两表排序 · 双指针按键归并 · 处理重复
Sort both relations, then merge with two pointers · one linear pass
LSM-tree · compaction
LSM-tree · compaction
memtable刷SSTable · 分层compaction · 去旧版本
Memtable fills, flushes to a sorted run, then leveled compaction merges and de-dups by version
Write-Ahead Logging · crash recovery
Write-Ahead Logging · crash recovery
先写日志再改页 · 崩溃REDO已提交/UNDO未提交
Log records are written before pages change; recovery redoes committed and undoes uncommitted transactions
Query plan cost
Query plan cost
顺序扫描vs索引扫描 · 连接顺序 · 估算行数选最优
Estimate rows scanned for alternative plans of a selection + join, and pick the cheapest
Two-phase locking (2PL) · lock table & deadlock
Two-phase locking (2PL) · lock table & deadlock
增长/收缩相 · 锁表 · 阻塞+死锁检测
Reads take a shared lock, writes an exclusive lock; conflicts block, a waits-for cycle is a deadlock
MVCC · snapshot isolation & version chains
MVCC · snapshot isolation & version chains
多版本行begin/end时间戳 · 快照可见版本 · 读不阻塞写
A read returns the version visible to its snapshot (begin_ts ≤ snapshot < end_ts) — readers never block writers
Conflict serializability · precedence graph
Conflict serializability · precedence graph
冲突优先图 · 环=不可串行 · 拓扑排序串行序
Build the conflict graph; a cycle means not serializable, acyclic gives a serial order by topological sort