数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

王争 2019-01-16
作为一个软件开发工程师,你对数据库肯定再熟悉不过了。作为主流的数据存储系统,它在我们的业务开发中,有着举足轻重的地位。在工作中,为了加速数据库中数据的查找速度,我们常用的处理思路是,对表中数据创建索引。那你是否思考过,数据库索引是如何实现的呢?底层使用的是什么数据结构和算法呢?

算法解析

思考的过程比结论更重要。跟着我学习了这么多节课,很多同学已经意识到这一点,比如 Jerry 银银同学。我感到很开心。所以,今天的讲解,我会尽量还原这个解决方案的思考过程,让你知其然,并且知其所以然。

1. 解决问题的前提是定义清楚问题

如何定义清楚问题呢?除了对问题进行详细的调研,还有一个办法,那就是,通过对一些模糊的需求进行假设,来限定解决的问题的范围
如果你对数据库的操作非常了解,针对我们现在这个问题,你就能把索引的需求定义得非常清楚。但是,对于大部分软件工程师来说,我们可能只了解一小部分常用的 SQL 语句,所以,这里我们假设要解决的问题,只包含这样两个常用的需求:
根据某个值查找数据,比如 select * from user where id=1234;
根据区间值来查找某些数据,比如 select * from user where id > 1234 and id < 2345。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(81)

  • Jerry银银
    听专栏,听到了自己的名字,不敢相信,看了文稿,确实是自己。真是受宠若惊!
    2019-01-16
    2
    180
  • Jerry银银
    个人觉得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,如果理解了那篇,这个问题应该不难。
    -------
    最后,我发现王争老师布置的这些课后思考题,都涉及到了之前学到的内容,不知道是有意还是无意的,嘻嘻!

    这节的思考题花了蛮多时间进行思考,才能给出以上答案,希望王争老师帮看看是否有不对的地方,谢谢!


    作者回复: 👍

    2019-01-19
    2
    69
  • 1.链表是双向链表,用以支持前后遍历
    2.散列表的节点用链表串起来,并不能实现范围查询,因为散列表本身无序,而B+树是基于二叉查找树演变而成,是有序的
    2019-01-16
    51
  • 老杨同志
    问题一,双向链表,方便asc和desc。
    问题二,可以支持区间查询。java中linkedHashMap就是链表链表+HashMap的组合,用于实现缓存的lru算法比较方便,不过要支持区间查询需要在插入时维持链表的有序性,复杂度O(n).效率比跳表和b+tree差
    2019-01-17
    2
    16
  • Felix Envy
    看到留言里很多同学都说第二题答案是肯定的,有点不同意。
    如果区间边界值在在散列表中没有命中,那么就无法定位区间的起始节点。
    如有错误望指出~
    2019-02-18
    14
  • feifei
    老师,看了你的讲解,对于B+树的原理,我基本理解了,我又找了b+树的代码实现,也搞懂怎么回事了,当我看懂了,这个B+树的实现了之后,我就有个问题,这个B+树该如何保存到磁盘中呢?我搜索了好多,也没有找到相关的一个代码,你有这相关的资料吗?这种数据一般是如何保存的?谢谢

    作者回复: 我懂你的意思。具体我没研究过。我觉得可以直接存到文件里。节点在文件里的位置表示指针。我瞎猜的:)等我研究研究再说:)

    2019-01-24
    8
  • 朱东旭
    这里讲的仅仅是单列索引,实际项目中组合索引使用应该比单列索引多,组合索引版的B+树是如何实现的,这个重要的知识点似乎被遗漏了。
    2019-05-05
    4
  • Flash
    对于第二题,觉得Jerry银银的答案有问题,可能会误导其他人。希望老师能指正一下,我觉得用链表将散列表节点串起来,不能支持按区间查找。因为散列表的节点是无序的,除非先遍历把散列表的节点放到数组中,进行排序,再用LinkedHashMap遍历存储,这样链表中串的节点才是有序的,直接用链表串散列表节点,是不支持按区间查找的。
    2019-03-26
    1
    4
  • hnbc
    老师,我想问一下100叉树为什么是3次io操作,不应该是4次吗,100的4次方是1亿

    作者回复: 这...第一层索引节点可以放到内存里的,这样就3次了:)

    2019-03-13
    4
  • 复兴
    innodb的聚簇索引,不是将数据存储在叶子节点上嘛,这里又说叶子节点不存储数据。
    2019-07-14
    3
  • 唯她命
    老师,现在觉得 你画的图 都是B树 而不是B+树

    作者回复: 好像不是吧

    2019-01-30
    3
  • 唯她命
    老师 网上查到的资料 说有k个子树的中间节点包含有k个元素(B树中是k-1个元素)
    和你讲的不同

    作者回复: 咱不要太教科书化啊。理解思想最重要啊。我觉得我讲的没问题啊。

    2019-01-30
    3
  • Monday
    请问:
    第一段代码,第9行:
    PAGE_SIZE = (m-1)*4[keywordss 大小]+m*8[children 大小]
    1,这个8指的是引用(指针)占的内存大小吗?
    2,引用大小是怎么计算的?和机器是多少位的有什么关系吗?
    望争哥回复,谢谢!

    作者回复: 1. 是的
    2. 有关系的,就是用多少位表示一个存储地址

    2019-01-20
    3
  • Monday
    先回答思考题:
    1. 双向链表,为了支持在O(logn)时间复杂度删除节点
    2.支持按区间查找数据。那么问题来了,为什么mysql索引不采用散列表+双向链表的数据结果来实现呢?
    2019-01-17
    4
    3
  • 有朋自远方来
    1.利用磁盘预读功能2.主簇索引
    觉得这两点也很重要。
    2019-01-16
    3
  • 茴香根
    好开心,终于搞清楚经常见到的b+树结构了。从这一节看到对于大数据情况下,m的大小对查询速度有重要影响。如在一些一些特定场合是否可以通过增大内存页和磁盘页大小来进一步提升查询效率。对于思考题中hash做索引,我认为是可行的,但每次更新索引时,如果新进入的节点索引需要插入到相应的位置,要保持叶子链表的有序。
    2019-01-16
    3
  • yaya
    1从图上来看,b+叶结点串起来的是双向链表
    2不可以,因为散列表的是被mod后的,查询区间依然需要遍历所有结点
    以前学b+树的时候,完全不知道它为什么这样设计,感觉很奇怪,今天才明白是为了提供区间查询,优化操作次数。
    2019-01-16
    3
  • 小喵喵
    理论上讲,对跳表稍加改造,也可以替代 B+ 树,作为数据库的索引实现的。
    关于这个,我简单说下我的理解:1.跳表的原始链表也都采用双向链表存储。2.跳表的层数是动态增加(减少)。增加(减少)对应B+数中的节点的分裂(合并)。不知道我的理解对不对,或者还有那些那些考虑到的,请老师指点下。
    2019-11-21
    2
  • 嗯嗯
    对作者说的那个m云里雾里
    2019-03-20
    2
  • 唯她命
    应该是每个结点至少有[ceil(m / 2)]个孩子 而不是m / 2
    2019-01-30
    2
收起评论
81
返回
顶部