B-trees and database indexes (2024)
3 days ago
- #b-tree
- #database-indexes
- #mysql-performance
- B 树是 MySQL 和 MongoDB 等数据库管理系统中的基础数据结构，通过索引实现高效的数据查找。
- B 树将有序的键/值对存储在节点中，每个节点的大小与磁盘块相匹配，以优化持久化存储。
- B+ 树是 MySQL 中使用的一种变体，仅在叶节点存储值，通过链表支持顺序遍历，并在内部节点容纳更多键。
- MySQL 的 InnoDB 引擎将表数据存储在 B+ 树中，以主键作为树键；二级索引使用额外的 B+ 树。
- 选择顺序主键（如自增整数）而非随机键（如 UUID），可以减少 I/O 并提升插入和查询性能。
- 主键大小很重要：较小的键（如 BIGINT 与 UUID 对比）使每个节点能容纳更多键，从而形成更浅的树，实现更快的查找。
- InnoDB 使用缓冲池将页缓存在内存中，以减少磁盘 I/O，但最小化页面访问对于性能仍然至关重要。