48 | B+树：MySQL数据库索引是如何实现的？

个人觉得B+tree理解起来真不难，抓住几个要点就可以了： 1. 理解二叉查找树 2. 理解二叉查找树会出现不平衡的问题（红黑树理解了，对于平衡性这个关键点就理解了） 3. 磁盘IO访问太耗时 4. 当然，链表知识跑不了 —— 别小瞧这个简单的数据结构，它是链式结构之母 5. 最后，要知道典型的应用场景：数据库的索引结构的设计 还记得，在学生时代，不好好学数据结构的我，当看到这个高大尚的名词“B+tree”时，我心里无比惊慌：这东西貌似不简单。^_^ 那时，也有着王争老师说的这种情况：B-tree，这是B减树；肯定还有个正常的B树；B+tree，这是B加树；然后在我的脑海里面，想当然地认为，它们之间有着这样的大小关系：B-tree < B tree < B+tree ---------- 对于思考题，@老杨 大哥的回答我觉得很到位了。 我只做一下补充： 第一题： 对于B+tree叶子节点，是用双向链表还是用单链表，得从具体的场景思考。我想，大部分同学在开发中遇到的数据库查询，都遇到过升序或降序问题，即类似这样的sql: select name,age, ... from where uid > startValue and uid < endValue order by uid asc(或者desc)，此时，数据底层实现有两种做法： 1）保证查出来的数据就是用户想要的顺序 2）不保证查出来的数据的有序性，查出来之后再排序 以上两种方案，不加思考，肯定选第一种，因为第二种做法浪费了时间（如果选用内存排序，还是考虑数据的量级）。那如何能保证查询出来的数据就是有序的呢？单链表肯定做不到，只能从头往后遍历，再想想，只能选择双向链表了。此时，可能有的同学又问了：双向链表，多出来了一倍的指针，不是会多占用空间嘛？ 答案是肯定的。可是，我们再细想下，数据库索引本身都已经在磁盘中了，对于磁盘来说，这点空间已经微不足道了，用这点空间换来时间肯定划算呀。顺便提一下：在实际工程应用中，双向链表应用的场景非常广泛，毕竟能大量减少链表的遍历时间 第二题： 答案是「肯定的」。如同@老杨 大哥说的，JDK中的LinkedHashMap为了能做到保持节点的顺序（插入顺序或者访问顺序），就是用双向链表将节点串起来的。 其实，王争老师在《散列表(下）》那一堂课中就已经深入讲解了LinkedHashMap，如果理解了那篇，这个问题应该不难。 ------- 最后，我发现王争老师布置的这些课后思考题，都涉及到了之前学到的内容，不知道是有意还是无意的，嘻嘻！ 这节的思考题花了蛮多时间进行思考，才能给出以上答案，希望王争老师帮看看是否有不对的地方，谢谢！

老师，看了你的讲解，对于B+树的原理，我基本理解了，我又找了b+树的代码实现，也搞懂怎么回事了，当我看懂了，这个B+树的实现了之后，我就有个问题，这个B+树该如何保存到磁盘中呢？我搜索了好多，也没有找到相关的一个代码，你有这相关的资料吗？这种数据一般是如何保存的？谢谢

老师，我想问一下100叉树为什么是3次io操作，不应该是4次吗，100的4次方是1亿

您好。有次面试，面试官直接问我，什么数据结构可以做到O(logn)的范围查询？ 当时没有想到填表，想到了B+树，而且数据库索引确实也是用的B+树。 那么问题来了，跳表和B+树在实现难度和性能上有什么区别，在数据量很大的情况下，表现性能如何，为什么redis选跳表？ 谢谢老师

请问： 第一段代码，第9行： PAGE_SIZE = (m-1)*4[keywordss 大小]+m*8[children 大小] 1，这个8指的是引用（指针）占的内存大小吗？ 2，引用大小是怎么计算的？和机器是多少位的有什么关系吗？ 望争哥回复，谢谢！

维持b+树的特性的策略有了，但是如何实现这个策略 以及一些其他问题解决的策略的实现 我有些发怵的感觉，大家一般都是怎么过来的呢？

老师，现在觉得 你画的图 都是B树 而不是B+树

老师 网上查到的资料 说有k个子树的中间节点包含有k个元素（B树中是k-1个元素） 和你讲的不同

叶子节点的数据是如何存储的？比如mysql的b+树，key放在一堆，data放在一堆？

对于这样的查询语句"select * from table where user_id < 1000", 是如何在叶子节点上进行遍历的？是找到1000之后往前遍历，还是从开始遍历到1000？