20200920——深入理解底层数据结构和算法

索引的定义

mysql官方对索引的定义是帮助mysql高效的获取数据的数据结构。

我们知道mysql的数据都是以文件的形式存储在磁盘上面的。
磁盘有一圈一圈的磁道。
磁头移动到不同磁道，磁盘旋转，这样就可以读到数据。
磁盘存取原理 1）寻道时间（速度慢，消耗时间） 2）旋转时间（速度快）
cpu读数据的时候都是从内存去读，内存再去磁盘里去读数据，内存读取数据大小都是一页的大小单位。

所以我们知道，每次磁头移动到另一个磁道取数据就是我们所谓的一次io操作，但是我们知道mysql的数据是分布到不同的磁道上的，每次读取数据都要把所有的磁道都读一遍，那么我们进行io次数就很多了，查询效率特别低。

那把索引就是把索引的地址保存起来，来帮助mysql直接定位到磁道哪个扇区，这样就减少了io操作，查询效率就高了。

数据结构那么多，为什么我们选用b+树数据结构

常见的数据结构

哈希表
b树
红黑树
二叉树
b+树

二叉树

二叉树是有n个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树组成。

不使用原因，会出现极端情况，一个节点只有一度，只有一个子节点，那读取的一层就是一次io，性能不好

红黑树

io效率太低

hash

没办法通过大小去筛选数据。

b树

没办法范围查询

b+树

所以的数据都存在叶子节点，非叶子节点不存储data，只存储key，可以增大度，顺序访问指令，提高访问的性能。

b+树的性能分析

一般使用磁盘的io次数评价索引结构的优劣。
预读：磁盘一般会顺序向后读取一定长度的数据（页的整数倍）放入内存。
局部性原理：当一个数据用到时，其附近的数据也通常会马上被使用了

不同的存储索引有不同的索引实现

myisam和innodb

myisam索引实现（非聚集索引）

索引文件和数据是分离的

innodb索引实现（聚集）