《48Bmore树：MySQL数据库索引是如何实现的？.pdf》由会员分享，可在线阅读，更多相关《48Bmore树：MySQL数据库索引是如何实现的？.pdf（17页珍藏版）》请在三一文库上搜索。
1、48|Bmore树：MySQL数据库索引是如何实现的？ file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/48Bmore树：MySQL数据库索引是如何实现的？.html2019/2/10 21:36:38 48|Bmore树：MySQL数据库索引是如何实现的？ 作为一个软件开发工程师，你对数据库肯定再熟悉不过了。作为主流的数据存储系统，它在我们的业务开发中，有着举足轻重的地位。在工作中，为了加速数据 库中数据的查找速度，我们常用的处理思路是，对表中数据创建索引。那你是否思考过，数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？ 算法解
2、析 思考的过程比结论更重要。跟着我学习了这么多节课，很多同学已经意识到这一点，比如Jerry银银同学。我感到很开心。所以，今天的讲解，我会尽量还原这个 解决方案的思考过程，让你知其然，并且知其所以然。 1.解决问题的前提是定义清楚问题 如何定义清楚问题呢？除了对问题进行详细的调研，还有一个办法，那就是，通过对一些模糊的需求进行假设，来限定要解决的问题的范围。 如果你对数据库的操作非常了解，针对我们现在这个问题，你就能把索引的需求定义得非常清楚。但是，对于大部分软件工程师来说，我们可能只了解一小部分 常用的SQL语句，所以，这里我们假设要解决的问题，只包含这样两个常用的需求： 根据某个值查找数据
3、，比如select * from user where id=1234； 根据区间值来查找某些数据，比如select * from user where id 1234 and id startValue and uid endValue order by uid asc(或者desc)，此时，数据底层实现有两种做法： 1）保证查出来的数据就是用户想要的顺序 2）不保证查出来的数据的有序性，查出来之后再排序 以上两种方案，不加思考，肯定选第一种，因为第二种做法浪费了时间（如果选用内存排序，还是考虑数据的量级）。那如何能保证查询出来的数据就是有 序的呢？单链表肯定做不到，只能从头往后遍历，再想想
4、，只能选择双向链表了。此时，可能有的同学又问了：双向链表，多出来了一倍的指针，不是会多 占用空间嘛？ 答案是肯定的。可是，我们再细想下，数据库索引本身都已经在磁盘中了，对于磁盘来说，这点空间已经微不足道了，用这点空间换来时间肯 定划算呀。顺便提一下：在实际工程应用中，双向链表应用的场景非常广泛，毕竟能大量减少链表的遍历时间 第二题： 答案是肯定的。如同老杨 大哥说的，JDK中的LinkedHashMap为了能做到保持节点的顺序（插入顺序或者访问顺序），就是用双向链表将节点串起来 的。 其实，王争老师在散列表(下）那一堂课中就已经深入讲解了LinkedHashMap，如果理解了那篇，这个问题应该
5、不难。 - 最后，我发现王争老师布置的这些课后思考题，都涉及到了之前学到的内容，不知道是有意还是无意的，嘻嘻！ 48|Bmore树：MySQL数据库索引是如何实现的？ file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/48Bmore树：MySQL数据库索引是如何实现的？.html2019/2/10 21:36:38 这节的思考题花了蛮多时间进行思考，才能给出以上答案，希望王争老师帮看看是否有不对的地方，谢谢！ 3赞 茴香根 2019-01-16 08:30:27 好开心，终于搞清楚经常见到的b+树结构了。从这一节看到对于大数据情况下，m的大小对
6、查询速度有重要影响。如在一些一些特定场合是否可以通过增大 内存页和磁盘页大小来进一步提升查询效率。对于思考题中hash做索引，我认为是可行的，但每次更新索引时，如果新进入的节点索引需要插入到相应的位 置，要保持叶子链表的有序。 3赞 老杨同志 2019-01-17 08:25:42 问题一，双向链表，方便asc和desc。 问题二，可以支持区间查询。java中linkedHashMap就是链表链表+HashMap的组合，用于实现缓存的lru算法比较方便，不过要支持区间查询需要在插入时维 持链表的有序性，复杂度O(n).效率比跳表和b+tree差 2赞 有朋自远方来 2019-01-16 19:
7、42:42 1.利用磁盘预读功能2.主簇索引 觉得这两点也很重要。 2赞 feifei 2019-01-24 08:58:25 老师，看了你的讲解，对于B+树的原理，我基本理解了，我又找了b+树的代码实现，也搞懂怎么回事了，当我看懂了，这个B+树的实现了之后，我就有个 问题，这个B+树该如何保存到磁盘中呢？我搜索了好多，也没有找到相关的一个代码，你有这相关的资料吗？这种数据一般是如何保存的？谢谢 1赞 作者回复2019-01-25 16:30:26 我懂你的意思。具体我没研究过。我觉得可以直接存到文件里。节点在文件里的位置表示指针。我瞎猜的：）等我研究研究再说：） Monday 2019-01
8、-20 08:23:47 请问： 第一段代码，第9行： PAGE_SIZE = (m-1)*4keywordss 大小+m*8children 大小 1，这个8指的是引用（指针）占的内存大小吗？ 2，引用大小是怎么计算的？和机器是多少位的有什么关系吗？ 望争哥回复，谢谢！ 1赞 Monday 2019-01-17 22:09:07 48|Bmore树：MySQL数据库索引是如何实现的？ file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/48Bmore树：MySQL数据库索引是如何实现的？.html2019/2/10 21:36:38 先回答思考
9、题： 1. 双向链表，为了支持在O(logn)时间复杂度删除节点 2.支持按区间查找数据。那么问题来了，为什么mysql索引不采用散列表+双向链表的数据结果来实现呢？ 1赞 刘章周 2019-01-16 09:11:21 我觉得是双向链表，sql语句中有按照从大到小进行排序，当使用索引进行排序时，如果是单向链表，还要把数据取出来放入内存中排序，效率降低，如果排 序的数据较多，内存不够，还会借助外部文件通过归并排序进行排序，效率很低。不知道说的对不对。 1赞 五岳寻仙 2019-01-16 08:33:00 课后思考题1 我觉得应该是双链表。对于区间查找，我们既需要支持大于某个值的查找(向右遍历
10、)，也需要支持小于某个值的查找(向左遍历)。 思考题2 我觉得不可以。因为散列表结点存储的数据是无序的。 1赞 yaya 2019-01-16 08:29:13 1从图上来看，b+叶结点串起来的是双向链表 2不可以，因为散列表的是被mod后的，查询区间依然需要遍历所有结点 以前学b+树的时候，完全不知道它为什么这样设计，感觉很奇怪，今天才明白是为了提供区间查询，优化操作次数。 1赞 K战神 2019-01-16 08:19:30 打卡 1赞 唯她命 2019-01-30 11:31:10 应该是每个结点至少有ceil(m / 2)个孩子 而不是m / 2 田伟 2019-01-29 18:49
11、:56 B+树和跳表很像，都是双向链表+索引的结构，数据都放在最下边，利用二分查找进行有序数列查找，区别是啥？我猜想主要区别在索引： 1.高度：同数量级的数据，跳表索引的高度会很高，IO读取次数多，影响查询性能 2.页空间浪费：mysql默认页空间16K,跳表默认一个节点只存一个数，其他空间都浪费了 睡痴儿 2019-01-26 21:44:31 那块b+树添加的部分如果是二叉树，且限定条件是节点的子节点都是两个的话，会出现最顶层有两个节点的情况啊 睡痴儿 2019-01-26 11:04:57 双向链表，这样方便查询。 也可以 48|Bmore树：MySQL数据库索引是如何实现的？ file
12、:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/48Bmore树：MySQL数据库索引是如何实现的？.html2019/2/10 21:36:38 呆梨 2019-01-23 13:53:47 打卡，老师从二叉查找树讲到了b树的由来，感觉以后再也不会忘记b树了，讲的很好 伟忠 2019-01-22 09:18:43 1，双向链表，需要支持大于，小于各种区间查询模式 2，可以，但维护索引，删除数据时间复杂度变高了，哈希只能精确定位，不支持区间查找。 每天晒白牙 2019-01-21 08:34:55 思考题1:双向链表，为了支持增序和降序 思考题2:可以支持范围查询，但需要保证跳表的数据有序 mysql数据库的索引一直是重点，这篇文章值得多读