mysql索引(一)

1、谈一下你对于mysql索引的理解？（为什么mysql要选择B+树来存储索引）

mysql的索引选择B+树作为数据结构来进行存储，使用B+树的本质原因在于可以减少IO次数，提高查询的效率，简单点来说就是可以保证在树的高度不变的情况下可以存储更多的数据：

1、在MYSQL的数据库中，表的真实数据和索引数据都是存储在磁盘中，我们在进行数据读写的时候必然涉及到IO的问题，IO本质上来说是硬件方面的问题，但是我们在做索引设计的时候肯定要尽可能的考虑如何提高IO的效率，一般来说，提高IO效率主要有两个维度的考虑，减少IO次数和减少IO量，所以要遵循这两个原则

2、我们在进行数据存储的时候量是没办法预估的，当表的数据量非常大的时候，我们是没有办法一次性将所有的数据都读取到内存中，因此这个时候就要采用分治的思想，将数据进行分块读取，一旦分块读取的话，我们就要考虑设计合理的块大小

3、数据在磁盘存储的时候有时间局部性和空间局部性的特性，内存跟磁盘在进行数据交互的时候也不是需要啥就读取啥，而是会把相关的数据全部都加载到内存中，在进行加载的时候有一个最基本的逻辑单位称之为页，页的大小一般是4KB或者8KB，跟操作系统相关，我们在数据读取的时候一般会选择页的整数倍读取，比如innodb存储引擎每次读取16KB的大小。这个特性刚刚好跟我们上述说的分块读取的设计观念吻合起来，因此块的大小会选择页的整数倍，在MYSQL中一般都是16KB的大小，当然也可以通过参数来进行调整，比如innodb中的innodb_page_size这个参数，当然一般情况下我们不会调整这个参数的大小

4、当块的大小确定了之后我们就要考虑数据格式了，我们在使用索引的时候基本是根据某一个或者多个索引列的值来进行整行数据或者部分字段的读取，比如select * from table where id = 10这个语句就是根据id的值去检索整行记录，因此整体的数据格式可以设计为K-V格式的数据，K值就是索引列的值，V值的设计就需要进一步思考了。

5、正常情况下，当需要从磁盘中读取某一行记录的时候，需要知道一些信息才能够定位到数据，比如：文件名称，偏移量，数据长度，当知道这些信息的时候就可以定位到任何一行记录，所以我们可以将V的值设计为刚刚的几个字段，但是要考虑一件事，如果将刚刚的那些信息作为索引信息的话，那么在进行数据读取的时候，首先要打开一个文件，读取到刚刚的那几个字段信息，然后再根据那些信息找到对应的数据文件读取具体的行数据，如果打开一次文件就是一次IO的话，至少需要2次IO操作才可以读取，这个跟我们上面所说的减少IO次数有点相违背，所以最好的方式是在V中直接将行记录进行存储，那么在读取数据的时候就可以直接根据K值读取到行记录，只不过此时需要将数据跟索引绑定存储，在MYSQL中，innodb存储引擎就是这样存储的，数据文件和索引文件全部位于后缀名为ibd的文件中

6、当数据格式确定了之后我们就需要思考使用什么数据结构存储了。支持K-V格式的数据结构有很多，比如哈希表，二叉树，BST，AVL，红黑树，但是MYSQL最终选择了B+树，下面我们要对比下各个数据结构之间的区别：

（1）使用哈希表可以进行数据存储，但是哈希表本质是无序散列表，因此在进行范围查询的时候就必须要挨个进行数据的对比，此时的效率是比较低的，此外，哈希表会存在哈希碰撞或者哈希冲突的问题，需要设计性能优良的哈希算法，因此哈希表并不适用，但是在MYSQL中，MEMORY存储引擎支持哈希索引，innodb存储引擎支持自适应哈希，

（2）二叉树、BST、AVL、红黑树这几种树也可以支持K-V格式的数据存储，但是它们有一个共同的特点就是至多只有两个分支，那么在进行数据存储的时候，一个三层的树至多可以存储7个数据结果值，这个数据太少了，如果想要存储更多的数据，只能把树的高度变高，而树的高度变高之后又会导致IO的次数变多，影响查询效率，那么我们就要思考如何在保证树的高度不变的情况下存储更多的数据，上述的这些树存储数据少的原因在于分支至多只有两个，那么我们就要思考改变分支的结构了，因此有了B-树。

（3）使用B-树之后，存储如下图所示：在每一个数据块中包含三种类型的数据，分别是key值，行记录和指针，当需要进行数据读取的时候只要一层一层向下检索即可：

在上图中，如果要读取28这条记录的话，那么只需要读取磁盘块1,3,8就可以把数据取出来，如果一个磁盘块大小是16KB的话，那么读取48KB的数据就可以获取到要查询的记录，此时我们就要思考，这样3层的B-树存满的情况下可以存储多少条记录了，假设一条记录是1KB的大小，那么第一层至多存储15条记录，第二层至多存储16（第二层的子节点个数）*15（每个节点可以存储的行记录树）=240条记录，第三层至多存储16*16*15=3840条记录，那么三层的树存满的情况下最多存储15+240+3840=4095条记录，此时存储的数据量依然不是很大，如果想要存储更多的数据的话就只能将树变高，变成4层或者5层，那么此时又会增加IO的次数，会影响查询效率，那么此时就要思考为何只能存储这么少的数据，经过分析之后发现，data占用了大量的空间，因此考虑使用B+树进行数据的存储

（4）使用B+树之后，存储如下图所示：将所有的data全部放到了叶子节点中，非叶子节点中只存储key值和指针的值，在进行检索的时候可以从根节点向下检索，也可以在叶子节点中从前向后或者从后向前检索：

在上图中，所有的data都在叶子节点中，也就说第一层和第二层省掉了大量的data的存储空间，那么可以存储更多的数据，假设一个data还是1KB的大小，一个key加上一个指针的大小为10个字节，那么我们可以来计算下可以存储多少数据，第一层一个数据块，第二层16*1024/10=1638个数据块，第三层1638**16*1024\10=2683044个数据块，第三层的每个数据块可以存储16条记录，那么最后的总记录数为42928704条记录，可以发现跟B-树的存储不是一个量级，在相同树高的情况下，B+树可以存储更多的数据

因此MYSQL最终选择了B+树做为数据结构来存储，在刚刚上述的计算公式中，我们做了一个假设，key+指针一共占了10个字节，如果占用100个字节的话，那么整体的数据会缩小2个量级，因此在回答索引的树的高度的时候不要说3层或者4层，给一个标准说法：一般情况下，3-4层的B+树足以支撑千万级别的数据量存储。