索引是什么？

索引是一种数据结构，可以快速地高效地查询，修改和删除数据表中的数据。

索引通过一定规则排列数据表中的记录，使得对数据的查询通过对索引的搜索来加快搜索速度。

索引使用的是什么数据结构？

B+树
为什么要使用B+树？而不使用其他数据结构？

关于搜索还有大数据的存储，一些基础数据结构的使用就无法有效地存储和查询。

例如

①顺序表、线性表，因为要使数据空间连续，所以存储数据的时候会浪费很多空间，因为需要扩容，在Java中，扩容时需要我们自己实现深拷贝，这时候会遍历整个数组，并且还要再开辟一段1.5倍/2倍的空间，时间的消耗会很高，也会有内存的浪费。虽然它的搜索速度很快，但是也会受首地址的影响，而且它的升删和插入的时间消耗也会很大。

②链表是一个线性存储的结构，它却可以避免空间的浪费，但是它的查询时间实在不稳定，是O(n)的时间复杂度，因为我们不知道该元素在表头还是表尾，如果是要查询表尾元素，但我们每次查询会从头来遍历的话，时间复杂度就变为了O(n)，即使是双向带头链表，依旧很难解决每次查询究竟需要从哪个位置查询，所以链式结构依旧不可以。

③二叉树型结构，
这里面有 二叉查找树、AVL树、红黑树，
它们的存储不会浪费多余空间，查询也很快，但是它们不适合存储大量的数据了。
像二叉查找树，它在树最偏的一边快的情况下，查询会变成O(n)的时间复杂度，因为它没有AVL的左旋和右旋。这就是二叉搜索树的最坏情况。

④多叉树型结构
典型的 B+树，MySQL 使用的就是 B+树。

B+树的数据结构是一个多叉树 + 叶子结点由链表连接的数据结构，在课上讲的是“多叉树 + 叶子结点单链表连接”的数据结构，但在MySQL 把它优化成了“单链表→双链表”可以广泛遍历了，因为非叶子结点所存储的都是值的引用，最大的值还是在叶子结点，所以每次查询或更新数据都必须在叶子结点上，此时时间复杂度稳定，都是O(log n)，修改和更新也很高效，而且，B+树是一个多叉树，它的结构框架时矮胖型的，相同高度下它的存储就会很大，所以保证了大数据的存储下的存储，和大数据的情况下，查询和更新数据的时间复杂度稳定。

索引的本质（用空间换时间）

优点：

• 可以大幅提升查询、排序、分组的效率

• 减少数据库扫描的数据量，降低服务器负载
但是：它会占用额外的磁盘资源，就像主键索引、普通索引都需要单独存储
降低插入、更新、删除的效率，每次修改数据，都需要同步修改索引的结构
在频繁更新的表中不建议使用索引，因为这时候，直接遍历反而会很快。