1.索引功能

转自：https://blog.csdn.net/qq_39871711/article/details/105356927

索引的作用是做数据的快速检索，而快速检索的实现的本质是数据结构。通过不同数据结构的选择，实现各种数据快速检索。 

比如上面这个数据表，如果 Mysql 没有实现索引算法，那么查找 id=7 这个数据，那么只能采取暴力顺序遍历查找，找到 id=7 这个数据需要比较 7 次，如果这个表存储的是 1000W 个数据，查找 id=1000W 这个数据那就要比较 1000W 次，这种速度是不能接受的。

2.索引实现的数据结构

2.1 哈希算法

哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的 key 地址，通过这个地址获取数据。

 哈希索引的过程：

select  *  from user where id=7;

• 哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231，
• 而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存储的额数据的物理地址，
• 通过该独立地址可以找到对应 user_name='g'这个数据。

 但是哈希无法实现范围查找，

select * from user where id >3;

2.2 BST二叉查找树

普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 O（N），检索性能急剧下降。

2.3 AVL 树和红黑树

两者都会自动旋转保持平衡，红黑树在顺序插入时会存在右倾的趋势：

 AVL， AVL 树是个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能会更多。

 AVL 树顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 4。从查找效率而言，AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。从树的形态看来，AVL 树不存在红黑树的“右倾”问题。也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。

总结一下 AVL 树的优点：

1. 不错的查找性能（O（logn）），不存在极端的低效查找的情况。

2. 可以实现范围查找、数据排序。

数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=16 这个数据我们就要进行磁盘 IO 四次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。【二叉树中的节点不是连续存储的，是离散的】

磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

2.4 B树

每个节点可以存储多个key。

总结来说，B 树用作数据库索引有以下优点：

1. 优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；

2. 尽可能少的磁盘 IO，加快了检索速度；

3. 可以支持范围查找。

2.5.B+树

B 树和 B+树有什么不同呢？

第一，B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。

第二，B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。【便于顺序查找吧？】

过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。

其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。

因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

2.5.1 B+树从磁盘读取

转自：https://www.cnblogs.com/luckgood/p/8979088.html

大多数人可能认为肯定还是B+树快，毕竟存储同样多的数据，100阶的B+树肯定比平衡二叉树的高度要低的多。但是别忘了B树在一个结点可能需要比较很多次才能找到下一层的结点，但是平衡二叉树只要比较一次就可以向下走一层。所以综合起来，其实两者索引的速度几乎（甚至说就是）是一样的。

那么我们为什么还要使用B+树呢？这是因为上面说索引速度相当的前提是两者的数据结构都位于内存中，当我们要在磁盘上索引一个记录时，将磁盘中的数据传输到内存中才是花费时间的大头，而在内存中的索引过程所花的时间基本是可以忽略不计的。【磁盘IO是主要的限制】

主存和磁盘之间的数据交换不是以字节为单位的，而是以n个扇区为单位的（一个扇区有512字节），通常是4KB（8个扇区），8KB（16个扇区），16KB，……64KB为单位的。假设，我们现在选择4KB作为内存和磁盘之间的传输单位，那么我们在设计B+树的时候，不论是索引结点还是叶子结点都使用4KB作为结点的大小。

我们这时不妨再假设一个记录的大小是1KB，那么一个叶子结点可以存4个记录。而对于索引结点（大小也是4KB），由于只需要存key值和相应的指针，所以一个索引结点可能可以存储100~150个分支，我们不妨就取100吧。当然这和上面第2节和第三节中的情况不太一样，因为现在索引结点的阶数是100，而叶子结点的阶数是4，两者并不一致，但这并没有什么问题。

 我们考虑如上图所示的B+树，下面的B+树有三层，两层是索引结点，最后一层是叶子结点。那么这个三层的B+树最多可以存400万个记录。

100*100*100*4=400w？

如果这个B+树存储到硬盘中，我们怎么根据记录的key找到对应的记录呢？

1. 首先我们要读取这个B+树的根结点到内存（花费一个IO的时间）然后在内存中进行索引，然后根据key找到对应的分支；
2. 将这个分支所指向的第二层索引结点读取到内存中（花费第二个IO时间）然后在内存中进行索引；
3. 根据key找到对应的分支，而这个分支指向的就是叶子结点，我们最后将这个叶子结点读取到内存中（花费的第三个IO时间）判断是否存在这个记录。

综上，只需3次IO。快速的原因是，索引结点中不存数据，只存键和指针，所以一个索引结点就可以存储大量的分支，而一个索引结点只需要一次IO即可读取到内存中。

当记录的大小可变时，叶子结点中记录该如何存储？

• 文件系统及数据库中的B+树是不考虑阶数这一个概念的，结点（即包括叶子结点，也包括索引结点）中仅遵行一个规则，如果剩余空间够大那么就存入数据，如果剩余空间不够，只能分裂后再存入。当B+树存储在磁盘中的情况时，IO效率才是第一要考虑的因素。CPU在某个结点内部多比较几次或少比较几次和IO花费的时间相比就不值得一提了。
• 如果某条记录太大，即使叶子结点中还剩余一多半的空间但仍然存不下怎么办？这个时候MySql称之为行溢出，简单的解决方式就是把记录存储在溢出页（磁盘的其它空闲地方）中，然后叶子结点中存储的是这个记录的指针。