索引的底层实现原理

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

MySQL支持两种索引，一种的B-树索引，一种是哈希索引，大家知道，B-树和哈希表在数据查询时的效率是非常高的。
这里我们主要讨论一下MySQL InnoDB存储引擎，基于B-树（但实际上MySQL采用的是B+树结构）的索引结构。
B-树是一种m阶平衡树，叶子节点都在同一层，由于每一个节点存储的数据量比较大，索引整个B-树的层数是非常低的，基本上不超过三层。
由于磁盘的读取也是按block块操作的（内存是按page页面操作的），因此B-树的节点大小一般设置为和磁盘块大小一致，这样一个B-树节点，就可以通过一次磁盘I/O把一个磁盘块的数据全部存储下来，所以当使用B-树存储索引的时候，磁盘I/O的操作次数是最少的（MySQL的读写效率，主要集中在磁盘
I/O上）

B-树

从上图可以看到B-树存在的缺点：

• 每个节点中有key，也有data，但是每一个节点的存储空间是有限的，如果data数据较大时会导致每个节点能存储的key的数据很小
• 当存储的数据量很大时同样会导致B-树的高度较大，磁盘IO次数花费增大，效率降低

B+树

那么MySQL最终为什么要采用B+树存储索引结构呢，那么看看B-树和B+树在存储结构上有什么不同？

1. B-树的每一个节点，存了关键字和对应的数据地址，而B+树的非叶子节点只存关键字，不存数据地址。因此B+树的每一个非叶子节点存储的关键字是远远多于B-树的，B+树的叶子节点存放关键
   字和数据，因此，从树的高度上来说，B+树的高度要小于B-树，使用的磁盘I/O次数少，因此查询会更快一些。
2. B-树由于每个节点都存储关键字和数据，因此离根节点进的数据，查询的就快，离根节点远的数据，查询的就慢；B+树所有的数据都存在叶子节点上，因此在B+树上搜索关键字，找到对应数据的时间是比较平均的，没有快慢之分。
3. 在B-树上如果做区间查找，遍历的节点是非常多的；B+树所有叶子节点被连接成了有序链表结构，因此做整表遍历和区间查找是非常容易的。

哈希索引

哈希索引当然是由哈希表实现的，哈希表对数据并不排序，只能进行等值比较，因此不适合做区间查找，效率非常低，需要搜索整个哈希表结构。

聚集索引与非聚集索引

MyISAM的索引方式叫做非聚集索引。

MyISAM

主键索引
MyISAM引擎使用B+树作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：

辅助索引
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

根据上图，首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

可以看到，MyISAM存储引擎，索引结构叶子节点存储关键字和数据地址，也就是说索引关键字和数据没有在一起存放，体现在磁盘上，就是索引在一个文件存储，数据在另一个文件存储，例如一个user表，会在磁盘上存储三个文件 user.frm（表结构文件） user.MYD（表的数据文件） user.MYI（表的索引文件）。

InnoDB

InnoDB的索引树叶节点包含了完整的数据记录，这种索引叫做聚集索引。
主键索引
InnoDB存储引擎的主键索引，叶子节点中，索引关键字和数据是在一起存放的，如图：

辅助索引
InnoDB的辅助索引，叶子节点上存放的是索引关键字和对应的主键，如图：

辅助索引的B+树，先根据关键字找到对应的主键，再去主键索引树上找到对应的行记录数据。从索引树上可以看到，InnoDB的索引关键字和数据都是在一起存放的，体现在磁盘存储上，例如创建一个user表，在磁盘上只存储两种文件，user.frm（存储表的结构），user.ibd（存储索引和数据）。

InnoDB的索引树叶节点包含了完整的数据记录，这种索引叫做聚集索引。因为InnoDB的数据文件本身
要按主键聚集，所以InnoDB要求表必须有主键（区别于MyISAM可以没有），如果没有显式指定，则
MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动
为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

自适应哈希索引

InnoDB 存储引擎监测到同样的二级索引不断被使用，它会根据这个二级索引树(B+树)上的二级索引值，在内存上构建一个哈希索引，来加速搜索。