1.初识MySQL索引

MySQL的索引的建立对MySQL的高效运行时很重要的，索引可以大大提高MySQL的检索速度

打个比方，如果合理的设计且使用索引的MySQL是一辆兰博基尼的话，那么没有设计和使用索引的MySQL就是一个人力三轮车。

拿汉语字典的目录页（索引）打比方，我们可以按拼音、笔画、偏旁部首等排序的目录（索引）快速查找到需要的字。

索引分单列索引和组合索引。单列索引，即一个索引只包含单个列，一个表可以有多个单列索引，但这不是组合索引。组合索引，即一个索引包含多个列。

2.索引的劣势

索引的主要目的就是提高查找效率，但是效率提高了，总是要付出一些代价

索引就相当于书的目录，对于一般的书目录比较少，但是如果内容巨大呢，就要耗费许多纸张来创建目录，索引也是这样，对于企业的数据库，数据量一般都特别的大，索引消耗的空间也就特别的大，而后续对数据库的内容进行修改，同样也需要对索引进行修改，拖慢了整体的增删查改

3.和索引相关的一些sql

--查看索引
show index from 表名;

--创建索引
creat index 索引名字 on 表名（列名）;

--删除索引
drop index 索引名字 on 表名;

创建和删除索引是一件非常低效的事，尤其是当前表里已经有很多数据的时候，如果未来在公司操作线上数据库，如果这个表没有索引不能贸然的去创建和删除索引

4.索引背后的数据结构

4.1HashTable

我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。但是哈希表并不能作为范围查找以及“大于小于”的数据库所使用

4.2.顺序表和链表

根据顺序表和链表的结构，想要查找就必须要遍历，显然也不符合我们的要求

4.3.二叉搜索树

关于二叉搜索树：每个父节点最多有两个子节点，左子树的值小于右子树

但是二叉搜索树的时间复杂度是o（n），这是为什么呢？

一般我么所说的二叉搜索树的时间复杂度是考虑最坏的情况，那就是二叉搜索树变成一个单枝树

如果是一个单枝树，当数据越多的时候，树的高度就越来越高，而高度就对应这比较次数，就大大增加了磁盘IO

磁盘IO的概念_letterwuyu的专栏-CSDN博客_磁盘io

4.4.AVL树

AVL树是一颗高度平衡的二叉树。

既然解决了搜索树变成单枝树的可能，那么用AVL树应该就可以了吧，但是结果依旧不行

理由：

1.AVL树的时间复杂度是logN。树的高度有多高，数据库就要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作，树的高度就相当于磁盘IO的次数，磁盘每次寻道时间为10ms。假设有一百万个数据，logN就等于20，time = 20 * 0.1 = 2s。这只是一百万的数据，对于一般的企业来说，数据的数量远不止一百万。

2.平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。那如何降低树的高度呢？