26｜B+ Tree：PostgreSQL 的索引是如何建立的？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
过去几讲我们学习了一些经典的分布式算法，主要涉及多个节点之间的协作方式，在现在的业务场景下，它们更多被封装在各种中间件或者类库中，直接供我们使用，不过背后的很多思想还是很值得好好学习体悟的。
从今天开始，我们将更加贴近日常业务开发，剖析常用中间件里用到的、单机上的一些算法，帮助自己更好地分析和优化系统性能。比如在使用数据库的时候，如果我们不清楚底层索引的原理，写出来的查询语句可能性能会很差，甚至不见得能正确建立索引；再比如有时候我们希望不引入额外的网关组件，直接在业务代码里实现一个简单的限流模块，如何设计更合适……
类似场景还有很多，话不多说，今天我们一起来了解这些中间件的秘密。
数据库
我们先从数据库聊起。数据库，应该是我们广大程序员日常开发中必不可少的组件了，作为数据持久化的基石，在互联网应用中，大部分的业务数据都以结构化的方式存储在数据库中，而数据库为我们提供了良好的数据查询、管理、持久化、事务的能力。
在数据库场景下，我们存储的都是大量的数据，显然没有办法一次性把所有的数据全部加载到内存中，用内存高效的数据结构或者算法进行搜索。那数据库是如何快速查询数据的呢？比如：
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
B+树在数据库索引中的重要性和应用价值是本文的重点。文章首先介绍了数据库索引的作用，以及线性稀疏的索引和红黑树在内存中的应用。随后详细介绍了B-树和B+树的结构和特点，以及B+树相对于B-树的优势，包括利用磁盘预读能力和树状结构降低查询的IO次数。文章还给出了B+树的检索过程伪代码，强调了其在大数据表中进行快速检索的优势。此外，文章还讨论了B+树的插入和删除操作，以及B+树在数据库中的高效变动和存储特性。总的来说，B+树通过空间换时间的思路，为数据表建立有序索引结构，加速查询效果，特别适用于数据库中需要频繁增删改数据的场景。文章内容深入浅出，对于读者理解数据库索引和优化系统性能具有一定的参考意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
麋鹿在泛舟不能少于m/2实际上是和约束"不能多余m"对称的，当一个叶子节点索引个数为m个，触发了m阶B+树的分裂操作，而分裂后的两个叶子节点元素的个数应该是m/2个： * 如叶子节点最少数量比m/2还大，那么就返回分裂和合并了。 * 如叶子节点最少的数量比m/2小很多，那么会大幅度降低合并的效率，导致很多少元素叶子节点。作者回复: 写得很好哦～
2022-03-064
那时刻我觉得m/2类似于二分查找里的采用二分而不是三分，更快的达到均衡。 另外一个观点是从信息论角度来看，二分的墒最大。2022-02-22- Paul Shan个人觉得这里每个节点包含的键值至少m/2,m/3,2*m/3对于查询的量级没有影响，都是lg n，m/2实现最简单，所以被选择。m/3的实现除了实现复杂还会增加层数，也就是io访问次数，最先被排除。2*m/3能够让某些情况下层数比m/2会少一些，但是意义不大，因为选择m本身已经降低了层数，选择合适的m，层数的问题已经解决，没有必要再在因子增加新的选择，2*m/3选择会让树的调整次数增加，实现复杂度增加。请问老师实际情况是不是这样?2022-02-22
收起评论
