4 MySQL学习---MySQL索引 _生活百科

ps：没有特殊说明，此随笔中默认采用innoDB存储引擎中的索引，且索引都是指B+树（多路平衡搜索树）结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用B+树，统称为索引。
索引概述索引是存储引擎用于快速找到记录的一种数据结构。
如下图所示：

文章插图
图中左边是数据表，一共有2列7行数据，最左边的0x09格式的数据是物理地址（注：逻辑上相邻的记录在磁盘上也不一定是物理相邻的）。为了加快Col2列数据的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据的物理地址的指针，这样就可以使用二叉查找树来快速获取到对应的数据。

要理解MySQL中索引是如何工作的，最简单的方法就是去看看一本书的“索引”部分：如果想在一本书中找到某个特定主题，一般会先看书的“索引” ，找到对应的页码。

索引对于良好的性能非常关键。尤其是当表中的数据越来越大时，索引对性能影响愈发重要。在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急剧下降。
一般来说索引本身占用也较大，不可能将全部索引存储在内存中，因此索引往往以索引文件（注：存储引擎是MYISAM时，索引单独存储在.myi文件中；存储引擎是InnoDB时，索引和表数据一起存储在.ibd文件中）的形式存储在磁盘上。索引是数据库中用来提高性能的最常用的工具。
为什么需要索引不使用索引，MySQL 就必须从第一条记录开始读完整个表，直到找出相关的行。表越大，查询数据所花费的时间就越多。如果表中查询的列有一个索引，MySQL 就能快速到达一个位置去搜索数据文件，而不必查看所有数据，这样将会节省很大一部分时间。
建立索引的优势与劣势优势

类似于书籍的目录索引，提高数检索的效率，降低数据库的IO成本。
在实现数据的参考完整性方面可以加速表与表之间的连接。
在使用分组和排序进行检索的时候，可以减少查询中分组和排序的时间.

劣势

实际上索引也是一张表，该表中保存了主键和索引字段，并指向实体类的记录，因此需要占用物理空间。数据量越大，占用空间就越大。
创建和维护索引都需要耗费时间，这种时间随着数据量的增加而增加。
虽然创建索引大大提高了查询的效率，同时却也降低了更新表的速度，例如对表进行insert、update、delete等操作。因为更新表时， MySQL不仅要保存数据，还需要保存索引文件每次更新的索引列的字段，动态调整因为更新所带来的键值变化后的索引信息。

索引的底层数据结构索引的底层数据结构是B+树。在学习它之前需要了解它的由来。
二叉查找树的引入首先，我们来看二叉查找树。
二叉查找树有这样的特点：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉查找树。

普通二叉查找树如下图所示：

文章插图
二叉查找树如果是完全二叉树，查找的效率很高，时间复杂度为O(log2N) 。因为最多只需要查找到树的log2N深度层。
但是当二叉查找树为单支树时，其退化为链表，此时它的深度为N，时间复杂度为O(N) 。
此时的二叉查找树如下图所示：

文章插图
因此，需要平衡二叉树来降低最坏情况下二叉查找树的深度。
平衡二叉树（AVL树）的引入平衡二叉查找树除了具备二叉查找树的特点，最主要的特征是树的左右两个子树的层级最多相差1 。其在插入删除数据时通过左旋或右旋操作来保持树的平衡，不会出现左右子树一边很高、一边很矮的情况。
平衡二叉树如下图所示：