为什么InnoDB选择B+树做索引更加高效
B+树索引介绍
InnoDB 存储引擎的最小储存单元是页（Page），一个页的大小是 16K。InnoDB存储引擎的所有数据文件（后缀为 .ibd 的文件），它的大小始终都是 16K的整数倍。页的大小一般也是可以设置的，如下命令可以查看当前页的大小。
数据表中的数据存储在页中，假设一行数据的大小是 1K，那么一个页可以存放 16 行这样的数据。如果数据库只按这样的方式存储，那么查找数据将是一个问题，因为我们不知道数据存储在哪个页中，也不可能所有的页都遍历一遍。那样做就太慢了。为了解决这个问题，数据库系统维护了一种特殊的能够满足某种高级查找算法的数据结构，这个数据结构以某种方式指向具体的数据。我们把这个数据结构称为索引。
在InnoDB存储引擎支持三种常用索引
- 哈希索引
- 全文索引
- B+树索引
InnoDB会根据表的情况自动生成哈希索引，不能人为干预表生成哈希索引
全文索引是将存在数据库的整本书的任意内容信息查找出来的技术，InnoDB从1.2.x版本支持。每张表只能有一个全文检索的索引。
B+树索引是传统意义上的索引，关系型数据库系统中查找最为常用也是最为高效的索引。它的构造类似于二叉树，根据键值对（key, value）查找数据。其中的B不是Binary，而是Balance的意思。它的本质就是B+树在数据库中的实现。它有一个特点就是高扇出性，因此在数据库中，B+树的高度一般是2-4层，也就是说查找某一键值对应的行记录只需要2-4次IO。
B+树是为了磁盘及其他存储辅助设备而设计的一种平衡查找树，在B+树中，所有记录的节点按大小顺序存放在同一层的叶节点中，各叶子节点用指针进行连接。还是来个例子有个直观感受吧，下图的B+树，高度为2，每页存放4条行记录，扇出是5。
B+树的数据组织方式
B+树索引分为聚集索引(cluster index)和辅助索引(secondary index)，聚集索引按表的主键构造的B+树，叶子节点存放整张表的行记录数据，每张表只能有一个聚集索引。一般优化器更倾向采用聚集索引，因为直接就能获取行数据。下面我们以一个聚集索引的例子来理解B+树的数据组织方式。
假设有一张customer表，有id、name、age三个字段，表结构如下图所示：
那么B+树的数据方式组织如下图所示：
现将数据记录按主键进行排序，分别存放在不同页中（这里假设一个页只存放3条记录），可以看到，除了数据页以外还有存放键值和指针的页，比如图中page number=3的页，该页存放键值和指向数据页的指针。这样的数据组织形式，一般称为索引组织表。
那么，假设现在要查找一条数据，该怎么查，比如：
select * from where id=4;
在这里选择自增id来做主键，通过这课B+树来查找，首先查找根页。一般来说，每个表的根页位置在表空间中都是不变的，在这里也就是page number=3的页。找到根页后通过二分查找法，定位到id=4的页应该在指针P5指向的页中。将该页读入内存后，继续去page number=5的页中查找，即可查找到id=4的对应记录了。
所以InnoDB中，B+树组织及查询数据总结起来，主要有以下两点:
- 页可以用来存放记录，也可以用来存放键值+指针，所有记录的节点按照大小顺序存放在同一层叶子节点中，非叶子节点用来存放键值+指针，键值一般是页面中的最小值(Low Key);
- 索引组织表只能通过非叶子节点的二分查找法以及指针确定数据在哪个页中，然后通过把查找到的页读入内存后，再在内存中进行查找记录行。
为什么B+树比B树更适合做索引
B树也是多叉树结构，一种自平衡的树，而且B+树是从B树演化而来的，那么为什么不使用B+树的前身B树呢？从结构比较来看，B树相比B+树的一个主要区别就在于B树的分支节点上存储着数据，而B+树的分支节点只是叶子节点的索引而已。根据这个差别可以得出以下结论：
- 磁盘IO读写次数相比B树降低了
在B+树中，其非叶子的内部节点都变成了key值，因此其内部节点相对B 树更小。如果把所有同一内部节点的key存放在同一盘块中，那么盘块所能容纳的key数量也越多。一次性读内存中的需要查找的key值也就越多。相对来说IO读写次数也就降低了。 - 每次查询的时间复杂度是固定的
在B+树中，由于分支节点只是叶子节点的索引，所以对于任意关键字的查找都必须从根节点走到分支节点，所有关键字查询路径长度相同，每次查询的时间复杂度是固定的。但是在B树中，其分支节点上也保存有数据，对于每一个数据的查询所走的路径长度是不一样的，所以查询效率也不一样。 - 遍历效率更高
由于B+树的数据都存储在叶子节点上，分支节点均为索引，方便扫库，只需扫一遍叶子即可。但是B树在分支节点上都保存着数据，要找到具体的顺序数据，需要执行一次中序遍历来查找。所以B+树更加适合范围查询的情况，在解决磁盘IO性能的同时解决了B树元素遍历效率低下的问题。
B+树作为索引可以存放多少数据
有道面试题，问InnoDB中，一颗的B+树可以存放多少行数据？
那么我们该如何计算呢？假设我们定义一颗B+树高度为2，即一个根节点和若干叶子节点。那么这课B+树的存放总行记录数=根节点指针数*单个叶子记录的行数。这里先计算叶子节点，B+树中的单个叶子节点的大小为16K，假设每一条目为1K，那么记录数即为16(16k/1K=16)，然后计算非叶子节点能够存放多少个指针，假设主键ID为bigint类型，那么长度为8字节，而指针大小在InnoDB中是设置为6个字节，这样加起来一共是14个字节。那么通过页大小/(主键ID大小+指针大小），即16384/14=1170个指针，所以一颗高度为2的B+树能存放18720条这样的记录。根据这个原理就可以算出一颗高度为3的B+树可以存放1170*1170*16=21902400条记录。所以在InnoDB中B+树高度一般为2-3层，它就能满足千万级的数据存储。
参加了CSDN APP 1024我身边的程序员话题活动，请大家帮我点赞，谢谢
转载：https://blog.csdn.net/songguangfan/article/details/102475002