理解MYSQL的索引

文章目录

一、索引的概念

索引是一种数据结构，包含对数据库中所有记录的引用指针，使用索引就可以快速的访问数据库表中的信息。通俗来说，一本书的目录就是一个索引表，读者可以通过目录快速的找到对应的章节内容。数据中，表、数据、索引的关系，类似于书架上图书、图书内容、目录的关系。可以对数据库表中的一列或者多列创建索引，快速定位，进行查找。

如果要查找数据，先使用索引查询。找到索引对应的物理地址，再进行具体内容的访问。减少了比较次数，加快比较效率。如果数据库没有使用索引进行查询，就是要将整个数据进行遍历去找到匹配的数据，这样效率会低很多。

二、索引的优缺点

1.优点

• 索引可以提高查找的效率，减少I/O次数
• 可以利用索引进行分组、排序，加快分组、排序

2.缺点

• 占用额外的存储空间，数据量越大，消耗的空间越大
• 虽然查找速度提高了，但是拖慢了增删改的效率。比如，增删改会使数据的内容发生变化，数据库不仅需要保存新的数据，同时也要保存索引对应的新的数据内容，调整索引结构。

三、使用场景

• 数据量较大，经常要进行对列的查询
• 数据表中的增删改操作，以及对列的修改频率比较低
• 索引存储在磁盘文件上，索引会占用额外的空间

满足以上条件可以创建索引，提高查找效率。反之，如果磁盘空间不足，或者对列的查询频率低，可以不考虑索引查询。

四、索引的使用

1. 查看索引 查看表中都有哪些索引

showindexfrom 表名;

1. 给某列创建索引

createindex 索引名 on 表名(列名);

但是，创建索引是一件低效率的事，尤其在数据量很大的时候

1. 删除索引

deleteindex 索引名 on表名;

五、索引背后的数据结构

如何实现索引与数据内容的对应关系？

• 顺序表和链表这两个数据结构，实现按值查找，需要进行遍历，效率是比较低的。但是顺序表按照下标访问元素，时间复杂度为O(1)，还是很快的，链表查找的时间复杂度为O(n)
• 二叉搜索树二叉搜索树最坏情况下的查找时间复杂度为O(n)，就是单枝树的情况。树的高度越高，比较次数也越多，以为者I/O次数增多最好情况： 复杂度：O(logn)最坏情况 复杂度：O(n)
• AVL树要求左右两颗树的高度差不超过1
• 红黑树 是要求更加宽松的平衡二叉树

二叉树最大的问题就是，数据很多的时候，树的高度高，比较次数多。而mysql的比较，就意味着磁盘I/O

• hash表 hash表的查找时间复杂度是O(1)，但是只能进行"相等"的查找，不能进行范围查找
• 堆 堆只能找出最大。或者最小的数据

所以，需要用树形结构，使用多叉搜索树。

• 多叉搜索树

首先，先介绍B树和B+树。

1、 B树

• 节点上会存储n个Key值，n个Key值对应n+1个区间，每个区间对应一个子树。
• B树的查找过程和二叉树非常相似。从根节点出发，根据待查找元素，确定查找区间，依次查找。
• 区别在于，二叉搜索树的查找效率和高度相关，每个节点比较一次。B树的高度虽然低了，但是每个节点比较多次，查询比较次数增多了，意味着磁盘的I/O次数也会增多。B树：

2、 B+树
与B树类似，做了改进。

B+树：

• n个节点，每个节点存储多个Key值，有n个区间
• 父节点在每一个子节点中都有体现
• 父节点中的值，会作为子节点的最大/最小值（示例为最大值）
• 最下面的叶子节点，使用链表进行顺序连接

B+树的优点

• 在数据量相同的情况下，B+树相对于B树更加“矮胖”。对于同一层来说，可以存储更多节点(索引)，整体的I/O次数是减少的。
• B+树的所有节点都保存在叶子节点中，中间节点只是查询的记录媒介，不存储真正的数据，所有的查询最终都落在叶子节点上。
• 叶子节点用链表进行顺序连接，提高了查找的效率，并且适合区间查找。
• B+树的查询比较稳定，有相同的I/O操作次数。每次查询都是从根节点到到叶子节点，因为所有的数据都在叶子节点中。B树的查找，性能不稳定，对于根节点的数据可能只进行一次I/O操作。但是对于叶子节点的数据，需要进行树的高度次I/O操作。
• 叶子节点存储数据，非叶子节点存储key值即可，因此非叶子节点占用的空间很小。

所以B+树比较适合存储数据库中的索引。