索引是什么索引是一种数据结构可以快速地高效地查询修改和删除数据表中的数据。索引通过一定规则排列数据表中的记录使得对数据的查询通过对索引的搜索来加快搜索速度。索引使用的是什么数据结构B树为什么要使用B树而不使用其他数据结构关于搜索还有大数据的存储一些基础数据结构的使用就无法有效地存储和查询。例如①顺序表、线性表因为要使数据空间连续所以存储数据的时候会浪费很多空间因为需要扩容在Java中扩容时需要我们自己实现深拷贝这时候会遍历整个数组并且还要再开辟一段1.5倍/2倍的空间时间的消耗会很高也会有内存的浪费。虽然它的搜索速度很快但是也会受首地址的影响而且它的升删和插入的时间消耗也会很大。②链表是一个线性存储的结构它却可以避免空间的浪费但是它的查询时间实在不稳定是O(n)的时间复杂度因为我们不知道该元素在表头还是表尾如果是要查询表尾元素但我们每次查询会从头来遍历的话时间复杂度就变为了O(n)即使是双向带头链表依旧很难解决每次查询究竟需要从哪个位置查询所以链式结构依旧不可以。③二叉树型结构这里面有 二叉查找树、AVL树、红黑树它们的存储不会浪费多余空间查询也很快但是它们不适合存储大量的数据了。像二叉查找树它在树最偏的一边快的情况下查询会变成O(n)的时间复杂度因为它没有AVL的左旋和右旋。这就是二叉搜索树的最坏情况。④多叉树型结构典型的 B树MySQL 使用的就是 B树。B树的数据结构是一个多叉树 叶子结点由链表连接的数据结构在课上讲的是“多叉树 叶子结点单链表连接”的数据结构但在MySQL 把它优化成了“单链表→双链表”可以广泛遍历了因为非叶子结点所存储的都是值的引用最大的值还是在叶子结点所以每次查询或更新数据都必须在叶子结点上此时时间复杂度稳定都是O(log n)修改和更新也很高效而且B树是一个多叉树它的结构框架时矮胖型的相同高度下它的存储就会很大所以保证了大数据的存储下的存储和大数据的情况下查询和更新数据的时间复杂度稳定。索引的本质用空间换时间优点• 可以大幅提升查询、排序、分组的效率• 减少数据库扫描的数据量降低服务器负载但是它会占用额外的磁盘资源就像主键索引、普通索引都需要单独存储降低插入、更新、删除的效率每次修改数据都需要同步修改索引的结构在频繁更新的表中不建议使用索引因为这时候直接遍历反而会很快。