B/B+树索引

索引由很多种类型，可以为不同的场景提供更好的性能。
在MySQL中，索引是在存储引擎层实现的，而不是在服务器层实现的，所以没有统一的索引标准。不同的存储引擎都有其侧重点，其工作方式也并不一样，其底层实现也可能不同。

MySQL支持两种索引，一种的B-树索引，一种是哈希索引，大家知道，B-树和哈希表在数据查询时的效率是非常高的。

数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘块（对应索引树的节点），索引树越低，越“矮胖”，磁盘IO次数就少

B树索引

B-Tree索引就是使用B-树数据结构来存储数据，实际上很多存储引擎使用的是B+树。

这里我们主要讨论一下MySQL InnoDB存储引擎，基于B树（但实际上MySQL采用的是B+树结构）的索引结构。

B树是一种m阶平衡树，叶子节点都在同一层，由于每一个节点存储的数据量比较大，索引整个B树的层数是非常低的，基本上不超过三层。

由于磁盘的读取也是按block块操作的（内存是按page页面操作的），因此B-树的节点大小一般设置为和磁盘块大小一致，这样一个B-树节点，就可以通过一次磁盘I/O把一个磁盘块也就是一个结点的数据全部存储下来，所以当使用B-树存储索引的时候，磁盘I/O的操作次数是最少的（MySQL的读写效率，主要集中在磁盘I/O上）。

一次磁盘IO一般需要经过以下几个过程：

1. 磁头移动到数据所在的磁道（寻道时间）
2. 找到目标磁道后通过盘面旋转，将目标扇区移动到磁头的正下方（旋转延迟）
3. 向目标扇区读取或写入数据（存取时间）

一次磁盘IO时间 = 寻道时间+旋转延迟+存取时间，主要花费时间都在寻道时间和旋转延迟上。而磁盘的存储是按block块操作的，我们希望的是一次磁盘IO能读出的有效数据最好是一个block块的大小。

在C/C++中，对应内存的申请，如果我们new/malloc向内存申请4个字节，实际上不可能只拿4个字节，内存管理是按页面4K为大小单位的，操作系统相当于批发站，它批发内存是以页面为单位的，我们申请4个字节，实际上我们向内核kernel申请，内核是按页面给我们分配的。按页面分配以后，但是我们的应用程序只需要4个字节，还剩下的字节就被libc.so或者 libc++.so库的ptmalloc（缓存），tcmalloc来管理（相当于内核版的内存池），相当于2个函数，管理剩下的空闲的字节，等你下次还malloc申请字节的时候，就不用向内核空间申请，直接在用户空间，从c库分配出来就可以了。等用光了，才向内核申请。

从磁盘存取的数据，都是来源于内存，所以一般磁盘block块的大小是内存page页的大小的整数倍。

B树和AVL树和红黑树，都是平衡搜索树，他们存储的数据都是有序的查询的时间复杂度都是O(logN)。但和AVL和红黑树不同，B树所有的叶子节点都在一层，它的孩子结点可以是m个。而索引的底层实现要用B树而不是AVL或红黑树的原因就在这。

假设我们现在要给一个存有2000w数据的表字段创建一个索引，假如用AVL来实现索引的存储，那么树的高度log2000w向上取整

要25层。
在最坏的情况下，也就是目标数据在最底层，从根节点开始往下一层一层的搜索，一次只加载了两个孩子结点的索引数据，一个磁盘block块一般能存储300~500个索引数据，但还是需要一次磁盘IO的时间。最终找到时需要花费25次磁盘IO的时间！

如果使用B树来创建索引，m为300，也就是300阶的B树，2000w的数据B树的高度为log2000w向上取整

高度只有3层。如果用B树来当索引的底层结构，结点所占空间大小最好是一次磁盘IO所能读取的最大大小，m的范围一般是300~500。
最坏的情况下，只需要3次磁盘IO就可以找到目标数据！

B+树索引

B+树是B树的一个变种，他们的不同点有：

1. B树的每一个节点，存了关键字和对应的数据地址，而B+树的非叶子节点只存关键字，不存数据地址。
2. B+树所有叶子节点被连接成了有序链表结构，存储关键字和数据地址。

B树

B+树

因为B+树的非叶子结点只存储关键字，不存储值，所以一个结点能存储的关键字就更多，相应的花费的磁盘IO次数就会有所降低。
B+树所有叶子节点被连接成了有序链表结构，关键字和信息都存储在叶子结点，所以每次查询花费的时间都非常平均，不会出现离根节点进查询就快，离得远就慢的问题。
因为关键字和信息都被串在有序链表上，因此是支持区间查询的，而且遍历所有结点也更加简单。
、、