mysql索引

数据库

1、mysql的索引的实现方式有哪些？

哈希实现，b+树实现，b树实现，但是最常用的还是b+树实现

2、什么因素决定了索引的实现方式，或者说是判断一个索引结构优劣的因素是什么

查找过程中磁盘io的操作次数
算法时间复杂度
而b+树的结构能够最大限度的在查找的过程中减少IO的次数

3、什么是b树和b+树

b树是一颗多路查找树

查找相关算法：先对根节点进行二分查找，然后再，找到则直接返回，如果没有找到，则找区间的指针。查找的时间复杂度接近O(logdn)(d是节点的度，n是所有的索引的数目，这里的(logdn)是指以d为底,不是d*n,之所以是这样，是因为每次在二分遍历了根节点之后，都能够排除 (d-1)*根节点树的 的节点 )
b+树和b树最主要的区别：内节点不存储data，只存储key;叶子节点不存储key，只存储data;b+树的叶子节点会通过指针连接在一起。

b+树的好处
b+树和b树相比，内节点不存储data（指向记录的指针），而是仅仅存储key，只有叶子节点是存储了data。这样的话，对于存储内节点的页，他所能够存储的key值和指针值也就越多，树的度也就越大，而查找效率是这样的logdN，这样的话d值越大，查找时间就越小了。同时b+树的叶子节点是相互连接在一起的，这样的话，对于范围查找来说，效率将会大大提高。

4、为什么b+树能够减少查询过程中io的操作次数

磁盘预读原理：每次读取数据的时候都是预读正数页的数据。
b树或者是b+树的大小刚好设置为一页。从而使得磁盘读取的次数最多为h(树高)。

缺点：写入性能较差

5、myisam和innodb的索引实现方式

相同点：都是使用b+树实现
不同点：myisam是的索引是非聚集索引；innodb的索引实现是聚集索引，主索引文件本身也就是数据文件。辅助索引文件对于存储不是地址，而是主键的值。所以通过辅助索引查找的话，需要访问两次索引，一次是主索引，一次是辅助索引。