索引的实现原理

心中有 B 树，才能学得更远...

索引是什么?

定义: 索引是帮助MySQL高效获取数据的数据结构。

快速定位数据，并查询出来，这是索引干的事。

索引的文件存储形式与存储引擎有关，

InnoDB 引擎的索引文件后缀是 .ibd ; MyISAM 引擎则是 .MYI

索引能快速定位数据，那它不是在内存中嘛？为啥保存在硬盘中呢？

因为硬盘相当于永久存储介质，可以保证意外断电或者发生故障重启不会造成索引数据丢失，而内存，它是RAM，断电数据会丢失的。

索引存储在硬盘中，但是MySQL服务启动，它会将整个索引文件加载到内存中，这样就可以快速地找到某个key ( 数据 )，再根据数据结构去硬盘中读取对应的数据。

当我们在硬盘上进行查询时，也就产生了硬盘的 I/O (读写)操作。相比于内存的存取来说，硬盘的 I/O 存取消耗的时间要高很多。当磁盘 I/O 次数越多，所消耗的时间也就越大。

所以，索引的数据结构设计目的是为了快速定位数据，并且去硬盘找数据时能少走 '弯路'

常见的数据结构有 Hash , B-tree ，B+tree ...

这里说下数据结构的实现原理

hash

把key转换为int 数据，取模运算，将key存储到hash表中，数据都会加载到内存中，数据表小，没啥问题，数据大，就会耗费大量内存空间，MySQL中采用的是“自适应Hash索引”的方式

B-tree

Balance tree(平衡多路搜索树)，在二叉树的基础上采用多叉树，这样可以降低树的深度，提高查询数据。

如下图，深度为3 ，所以查找数据最多需要对磁盘3次 I/O 操作。

B-tree

缺点

每个节点都有data(整条记录) , 节点空间有限，通常是16KB，如果data较大，会导致节点存储的数据更少，往往3层的深度存储的数据远远不能满足需求。

那就需要4层或更深的树，于是通过磁盘查找数据多了几次 I/O 操作，严重影响数据存取速度，而影响服务器性能。

于是，就有了B+tree ,读作 ' B plus 树 ’ , 它在B树的基础上做了一些优化。

B+树

1.每个节点可以包含更多的节点指针，降低树的深度，提高了 数据检索速度。

2.叶子节点中的数据顺序存储。三层，可存储百万到千万级别的数据量，基本上够用了

3.所有数据形成一个链式结构，顺序查询性能更高。

B+tree

索引的数据结构都有个小问题，如果索引的值是递增的，那么插入数据就会在新的叶子里插入，如果不是递增，就会将其中的页进行分列合并，旋转，因此索引的维护和更新比较麻烦。

这也是为什么需要给每张表添加自增的主键索引，因为自增，所以每插入一条记录，都是在末尾的叶子节点添加key，这样就避免了索引结构的分列而导致的性能问题。

存储引擎怎么实现数据结构的呢？

Innodb -- B+tree

叶子节点存储的是实际的data值

MyISAM -- B+tree

叶子节点存储的是数据的地址值，如同书籍的目录.根据地址找到对应的数据内容

关于B+树的数据结构的图解，可以看这个网址：

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

尝试着插入删除一些数据，了解它的执行过程。