B-Trees: Why Every Database Uses Them
6 months ago
- #data-structures
- #database
- #performance
- B树是数据库用于高效查找磁盘数据的基础数据结构，因为磁盘访问速度远慢于内存访问
- 二叉搜索树(BST)在磁盘上效率低下，因为每个节点访问都需要磁盘寻道，I/O开销过高
- B树通过高扇出特性(每个节点包含多个子节点)解决BST的缺陷，降低树高度并最小化磁盘寻道
- B树具有自平衡特性，其节点大小设计为匹配磁盘块(通常4KB到16KB)，从而优化磁盘I/O性能
- B树操作(查找/插入/删除)具有对数时间复杂度，能高效处理大规模数据集
- MySQL、PostgreSQL、SQLite和MongoDB等主流数据库采用B树(或其变种B+树)作为索引结构
- B树通过有序键值和叶子节点链表高效支持范围查询
- B树的权衡点包括节点分裂/合并时的写放大问题，以及缓存节点带来的内存开销
- 对于写入密集型场景LSM树更优，而内存数据库通常选择哈希索引或跳表
- 凭借性能、效率与范围查询支持的完美平衡，B树仍是磁盘存储领域的主导结构