MySQL索引底层结构与实现原理

上一篇 <<<Too many connections分析与processlist解读
下一篇 >>>

---

为什么要使用索引

MySQL官方定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构，类似于书的目录结构一样。
如果向mysql发出一条sql语句请求，查询的字段没有创建索引的话，可能会导致全表扫描，这样的话查询效率非常低。

索引的存放位置

索引是存放在硬盘上的/var/lib/mysql目录下
MyISAM引擎的文件：
.frm 表结构
.myd 即 my data，表数据文件
.myi 即my index，索引文件
InnoDB引擎的文件：
.frm 表结构
.ibd文件：存放用户数据库表数据和索引。

索引文件为什么要放到硬盘上?
a、可以永久保存
b、如果文件很大，放到内存中容易导致内存溢出

索引的数据结构【数据结构模拟】

1.Hash算法【等值查询效率较高，但不能进行范围查找】

下标index=Hash(key)，内容存具体的值，这样的数组叫做散列表，也叫哈希表，映射的函数叫做散列函数。
优点：通过字段的值计算的hash值，定位数据非常快。
缺点：不能进行范围查找，因为散列表中的值是无序的，无法进行大小的比较。

2.二叉树

特性：分为左子树、右子树和根节点，左子树比根节点值要小，右子树比根节点值要大，正常查询时间复杂度log2n
缺点：有可能产生不平衡 类似于链表的结构 时间复杂度为o(n)

2.平衡二叉树(AVL树)【效率还可以，同时解决了hash算法不能范围查找的问题】

特点：
a、它的左子树和右子树都是平衡二叉树
b、左子树比中间小，右子树比中间值
c、左子树和右子树的深度之差的绝对值（平衡因子）不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。

优点：平衡二叉树算法基本与二叉树查询相同，效率比较高
缺点：
a、插入操作需要旋转
b、支持范围查询，但回旋查询效率较低，比如要查找大于5的，会回旋到父节点6、8。
c、如果存放几百条数据的情况下，树高度越高，查询效率会越慢【核心原因是每个节点只存放一个数据】

查询原理【折半查找、二分查找】：
假设查询10 （需要经历4次IO操作）
1次 从硬盘中读取4 （内存），判断下10>4，取右指针
2次 从硬盘中读取8 （内存），判断下10>8，取右指针
3次 从硬盘中读取9 （内存），判断下10>，取右指针
4次 从硬盘中读取10 （内存），判断下10=10，定位到数据
规律：如果树的高度越高，那么查询IO次数会越多。

3.B树【节点增加元素，减少了树的高度，加快IO操作】

优点：B树的节点中可以有多个元素，从而减少树的高度，减少IO操作，从而提高查询效率
缺点：范围查询效率还是比较低。

4.B+树【解决范围查询问题、减少IO查询的操作】

和B树相比优点：
a、新增叶子节点与非叶子节点关系，叶子节点中包含了key和value，非叶子节点中只是包含了key，不包含value。
b、所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定顺序排序，从而范围查询效率非常高。
缺点：有冗余节点数据，所以会比较占用硬盘大小。但取舍相比，这样效率还是高的。

为什么MySQL底层要使用B+树索引结构

B+树索引具有范围查找和前缀查找的能力，相当于二分查找。
而Hash索引只能支持等于查询，无法支持范围查询，B树的范围查找使用回旋效率较低。

1.支持范围查询
2.降低树的高度 减少磁盘io的次数

MyISAM和InnoDB对B+Tree索引不同的实现方式

Myisam的key存放的是数据库的key，value存放的是数据库记录的地址，在通过地址定位到数据。
InnoDB的key存放的是数据库的key，value存放的是数据库记录的内容，相比MyISAM效率要高一些，但是比较占硬盘内存大小。

MySQL常用索引类型

Hash索引和B+树索引

MySQL的B+树能够存放多少字节数据

操作系统对数据的操作都是按页读取的，大部分是一页4K，Mysql的InnoDB页大小默认为16K，当然也可以通过参数设置：show variables like 'innodb_page_size'; 16384/1024=16kb;
如果读取内容超过1页就会读取2页，小于1页会读取1页，所以B+树的每一个节点是页的倍数是最佳的。

非叶子节点存放索引和指针，索引值(bigint 8b)和指针(6b)，一页16*1024/(8+6)=1170指针。

假设一行为1kb，那么一页可以读取16行数据，一个叶子节点可以存放16条数据

B+树 高度为2 117016=18720条数据
B+树 高度为3 11701170*16=21902400条数据（2千万）

所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

为什么InnoDb引擎表必须有主键，并且推荐使用整型的自增方式？

A.不建议使用uuid使用数据库主键，不支持范围查询
B.B+树底层搜索的时候可能会发生值比较判断

非主键索引是如何造成二次查找的？