How does B-tree make your queries fast?
3 months ago
- #database
- #indexing
- #performance
- B树是一种数据结构，能够高效搜索大量数据，广泛应用于现代数据库系统。
- B树与二叉搜索树(BST)不同，它允许每个节点存储多个值，并具有自平衡特性，从而优化查询性能。
- CPU缓存、内存和磁盘存储等硬件因素会影响B树的设计，以最小化随机访问并最大化顺序访问。
- 顺序访问速度显著快于随机访问（尤其在机械硬盘上），这使得B树的设计特别适合基于磁盘的存储系统。
- B树通过在每个节点（页）中打包多个值来降低树的高度，从而减少查询所需的磁盘读取次数。
- PostgreSQL采用8kB页大小设计，每页可存储约375个值，即使处理十亿级数据也只需4层树结构，实现高效存取。
- B树具备自平衡特性，在插入数据时通过节点分裂和值提升操作保持结构平衡，确保性能稳定。
- PostgreSQL对节点分裂进行了优化，最大限度减少空间浪费，提升存储效率。
- B树兼顾硬件效率与自平衡的设计理念，使其成为数十年来经久不衰的高效索引结构。