⾯试官：MySQL索引为什么要⽤B+树实现？
codeblocks下载原因如下
1. B+树能显著减少IO次数，提⾼效率
2. B+树的查询效率更加稳定，因为数据放在叶⼦节点
3. B+树能提⾼范围查询的效率，因为叶⼦节点指向下⼀个叶⼦节点
B+树是怎么来的？
在从⼀堆数据中查指定的数据时，我们常⽤的数据结构是哈希表和⼆叉查树，表本质上就是⼀堆数据的集合，所以MySQL数据库⽤了哈希表和B+树来实现索引
B+树是通过⼆叉查树，再由平衡⼆叉树，B树（⼜名B-树）演化⽽来的，B+树中的B不是代表⼆叉（binary），⽽是代表平衡（balance），因为B+树是从最早的平衡⼆叉树演化⽽来，但是B+树不是⼀个⼆叉树。
滑块滑轨卡
⼆叉查树和平衡⼆叉树
⼆叉查树的效率和平衡⼆叉树的查效率已经很⾼了，为什么不⽤这两种数据结构来实现索引呢？慢慢来分析
⼆叉查树是带有特殊属性的⼆叉树，需要满⾜以下属性
1. ⾮叶⼦节点最多拥有两个⼦节点
2. ⾮叶⼦节值⼤于左边⼦节点、⼩于右边⼦节点
3. 没有值相等重复的节点;
对上图这个⼆叉树进⾏查，如查键值为5的记录，先到根，其值时6，⼤于5，查6的左⼦树，到3，5⼤于3，再其右⼦树，⼀共了3次。同理，查键值为8的记录，⽤了3次。所有键值平均查次数为(1+2+2+3+3+3)/6=2.3次，假如对这些键值进⾏顺序查，平均查次数为(1+2+3+4+5+6)/6=3.3（查顺序摆放的数，第⼀个数肯定是1次，⽽第2个数是2次，以此类推），显然⼆叉查树的平均查速度⽐顺序查更快
⼆叉查树可以任意的构造，假如⼆叉查树按照如下⽅式构造
gitmind怎么样平均查速度为(1+2+3+4+5+5)/6=3.16次，和顺序查差不多。为了提⾼⼆叉查树的查询效率，需要⼆叉查数是平衡的，这就引出了平衡⼆叉树。
平衡⼆叉树除了满⾜上⾯3个属性，还要满⾜如下1个属性，树的左右两边的层级数相差不会⼤于1
平衡⼆叉树的查效率确实很快，但维护⼀颗平衡⼆叉树的代价是⾮常⼤的，需要1次或多次左旋和右旋来得到插⼊或更新后树的平衡性。简单举个例⼦。
初始平衡⼆叉树
数据库登录密码忘了怎么办
插⼊3
右旋⼀次
再左旋⼀次
作为⼀个科普性的⽂章，这⾥不对左旋的右旋的细节进⾏分析，放⼏个图⽚能理解左旋和右旋即可对y进⾏右旋，意味着将y变为⼀个右节点
对x进⾏左旋，意味着将x变为⼀个左结点
回头看上⾯例⼦的左旋和右旋，是不是很清楚了？
B树和B+树
B树和B-树是同⼀种树，假如⽤平衡⼆叉树实现索引效率已经很⾼了，查⼀个节点所做的IO次数是这个节点所处的树的⾼度，因为我们⽆法把整个索引都加载到内存，并且节点数据在磁盘中不是顺序排放的。所以最快情况下，磁盘的IO次数为数的⾼度。
虽然平衡⼆叉树查效率确实很⾼，但是频繁的IO才是阻碍提⾼性能的瓶颈，怎样减少IO次数呢？前新手如何建设网站
辈们很聪明的提出了局部性原理，分为时间局部性原理，即加⼊你查询id为1的⽤户数据，过⼀段时间你还会查询id为1的数据，所以会将这部分数据缓存下来。空间局部性原理，当你查询id为1的⽤户数据的时候，你有很⼤的概率会去查询id为2，3，4的⽤户的数据，所以会⼀次性的把id为1，2，3，4的数据都读到内存中去，这个最⼩的单位就是页。
简单来说CPU进⾏运算是电⼦运动，计算速度很快。⽽将数据从硬盘读取到内存中是机械运动，很慢。我们在买硬盘的时候经常问这个硬盘是多少转（每分钟转动的圈数），7200转，5400转。所以说转动的越快加载数据越快，但是和CPU⽐起来差的还很远，所以说要减低IO 次数。
B树和B+树的概念⽐较复杂，有兴趣的⼩伙伴可以点原⽂链接看看知乎上写的⼀篇⽂章，这⾥只做⼀个宏观的介绍
前⽂已经提到树⾼决定着IO的次数，那么降低树⾼不就能减少IO的次数吗，怎么减少呢，每个节点的数据多放⼀点不就⾏了，并且这个数据是存放在⼀块的，对应的是数据库中的读取的最⼩单位页，⼀次IO就可以将这些数据读取出来，虽然⽐较的次数有可能会增加，但是在内存中的⽐较和磁盘IO相⽐差⼏个数量级，整体上效率还是提⾼了
所以你看到的B树是这样的
B+树是这样的
那么B树和B+树的区别在哪呢？
1. B+跟B树不同B+树的⾮叶⼦节点不保存键值对应的数据，这样使得B+树每个节点所能保存的键值⼤⼤增加；
2. B+树叶⼦节点保存了⽗节点的所有键值和键值对应的数据，每个叶⼦节点的关键字从⼩到⼤链接（这个特性对范围查特别有利，范
围查只需要遍历链表即可，并不⽤像b树⼀样回旋查，例如先查5，再查6，再查7）
3. B+树的根节点键值数量和其⼦节点个数相等;
4. B+的⾮叶⼦节点只进⾏数据索引，不会存实际的键值对应的数据，所有数据必须要到叶⼦节点才能获取到，所以每次数据查询的次数
mysql面试题 知乎都⼀样；
放个图理解的更清楚⼀点
B树
B+树
在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有关键字指针都存在叶⼦节点，所以每次查的次数都相同所以查询速度更稳定。
除此之外，B+树的叶⼦节点是跟后序节点相连接的，这对范围查是⾮常有⽤的。
看到没B+树的⾮叶⼦节点是主键，主键占⽤的空间越⼩，每个节点能放的主键就能更多，这就是为什么我们的主键⼀般不设置太⼤的原因。主键占⽤的空间⼩，能降低树⾼，减少IO次数。
聚集索引和联合索引
在InnoDB存储引擎中，是以主键为索引来组织数据的。在InnoDB存储引擎中，每张表都有个主键，如果再创建表时没有显⽰的定义主键，则InnoDB存储引擎会按如下⽅式选择或创建主键。
1. ⾸先判断表中是否有⾮空的唯⼀索引，如果有，则该列即为主键
2. 如果不符合上述条件，InnoDB存储引擎⾃动创建⼀个6字节⼤⼩的指正作为索引
3. 如果有多个⾮空唯⼀索引时，InnoDB存储引擎将选择建表时第⼀个定义的⾮空唯⼀索引作为主键
假如说有如下数据，⽤户id为主键（1， tom），（2，mike），（3，sam），（4，lisa），（5，li）则数据是这样存储的，图1

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。