Mysql索引为什么采用B+树？索引为什么要自增？

1、索引作用是什么？使用什么数据结构存储？

【作用】：加快数据检索

【数据结构】：B+树

2、为什么使用B+树存储索引？

B+树减少了IO操作且底层节点是所有数据的有序排列，便于范围查找，排序查找，分组查找以及去重查找

首先，索引存储是k-v格式的，即索引-行数据，那么常见可以选择的数据结构有：hash表、二叉树、B树、B+树。

【hash表】

需要很优良的hash算法避免数据散列带来的浪费空间和查询快慢不均匀，并且hash表是无序的，相当于全表扫描，但是由于hash是在内存中进行的，所以即使如此依旧很快，但是核心问题就是在内存中太消耗内存。

【二叉树】

每个节点只有2个子树，如果数据量很大的时候，那树的层级就很深，查找次数会很大，影响查询速率。

【B树】

B树相当于二叉树来说，每个节点可以有多个子树，这样就保证了层级较浅，查询效率提高，但是，由于索引数据存在磁盘，查询需要IO操作，IO操作相对内存来说是非常慢的，因此需要尽量减少IO操作次数，因此读取数据是按照磁盘块(文件系统读写数据的最小单位)读取，而Innodb中页(内存的最小存储单位。页的大小通常为磁盘块大小的 2^n 倍)的默认大小是16kb，由于B树的页中存储的是k-v，大大降低了页中存储的索引数，因此，增加了IO操作次数，降低了查询效率。另外，B树的数据分散在各个节点，要实现范围查找，排序查找，分组查找以及去重查找相对较复杂，也降低了速率。

【B+树】

B+树除底层页以外，页中只存k，这样单页中就能存储更多的索引值，减少了IO操作，从而加快了查询速率。

因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。

这样如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。