深化理解 MySQL 索引底层原理 A8站源码交易平台
Mysql 作为互联网中十分抢手的数据库，其底层的存储引擎和数据检索引擎的规划十分重要，尤其是 Mysql 数据的存储方式以及索引的规划，决议了 Mysql 全体的数据检索功能。
何为索引
咱们知道，索引的作用是做数据的快速检索，而快速检索的完成的本质是数据结构。经过不同数据结构的挑选，完成各种数据快速检索。在数据库中，高效的查找算法是十分重要的，由于数据库中存储了许多数据，一个高效的索引能节约巨大的时刻。MySQL索引的树立关于MySQL的高效运转是很重要的，索引能够大大提高MySQL的检索速度。创立索引时，你需求确保该索引是应用在 SQL 查询语句的条件(一般作为 WHERE 子句的条件)。实际上，索引也是一张表，该表保存了主键与索引字段，并指向实体表的记载。A8站源码交易平台
怎么挑选Mysql 索引底层数据结构
哈希表
哈希表是做数据快速检索的有用利器。
哈希算法：也叫散列算法，便是把恣意值(key)经过哈希函数变换为固定长度的 key 地址，经过这个地址进行具体数据的数据结构。
考虑这个数据库表 user，表中一共有 7 个数据，咱们需求检索 id=7 的数据，SQL 语法是：
select * from user where id=7;
哈希算法首先核算存储 id=7 的数据的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 便是 id=7 存储的额数据的物理地址，经过该独立地址能够找到对应 user_name='g’这个数据。这便是哈希算法快速检索数据的核算过程。
处理哈希算法数据磕碰问题
处理磕碰问题的一个常见处理方式便是链地址法，即用链表把磕碰的数据接连起来。核算哈希值之后，还需求查看该哈希值是否存在磕碰数据链表，有则一向遍历到链表尾，直达找到真实的 key 对应的数据为止。
哈希算法的时刻复杂度为O(1),检索速度十分快，可是MySQL并没有挑选作为底层算法，为何？
由于考虑到数据检索有一个常用手法便是规模查找，比如以下这个 SQL 语句：
select * from user where id >3;
假如运用哈希算法完成的索引，规模查找的思路便是一次把所有数据找出来加载到内存，然后再在内存里挑选目标规模内的数据。可是这个规模查找的办法也太笨重了，没有一点功率而言，因而哈希索引是不适合作为 Mysql 的底层索引的数据结构。
二叉查找树(BST)
二叉查找树是一种支持数据快速查找的数据结构，时刻复杂度是 O(lgn)，从检索功率上看来是能做到高速检索的。此外二叉树的结构也能够处理哈希索引不能提供的规模查找功能，二叉树的叶子节点都是按序摆放的，从左到右顺次升序摆放，比如说需求找节点上 id>5 的数据，那咱们取出节点为 6 的节点以及其右子树就能够了，规模查找也算是比较容易完成。
可是普通的二叉查找树有个致命缺陷：极点情况下会退化为线性链表，二分查找也会退化为遍历查找，时刻复杂退化为 O（N），检索功能急剧下降。在数据库中主键字增是比较常见的方式，假如采纳二叉树这种数据结构作为索引，那上面介绍到的不平衡状况导致的线性查找的问题必然呈现。因而，简略的二叉查找树也不能直接用于完成 Mysql 底层索引的。A8站源码交易平台
AVL 树和红黑树
二叉查找树存在不平衡问题，能够经过树节点的主动旋转和调整，让二叉树始终坚持根本平衡的状况，就能坚持二叉查找树的最佳查找功能了，因而也能够联想到AVL树和红黑树。
红黑树是一颗会主动调整树形状的树结构，比如当二叉树处于一个不平衡状况时，红黑树就会主动左旋右旋节点以及节点变色，调整树的形状，使其坚持根本的平衡状况（时刻复杂度为 O（logn）），也就确保了查找功率不会显着减低，红黑树具有不错的均匀查找功率，也不存在极点的 O(n)情况，可是假如将红黑树作为Mysql 底层索引完成也是存在一些问题。
红黑树次序刺进 1~7 个节点，查找 id=7 时需求核算的节点数为 4。次序刺进 1~16 个节点，查找 id=16 需求比较的节点数为 6 次。当数据是次序刺进时，树的形状一向处于“右倾”的趋势，因而红黑树并没有完全处理二叉查找树“右倾”趋势，即使不是一个线性链表，由于这种现象关于查找功能而言是巨大的耗费，数据库不可能忍耐这种无意义的等待。
AVL树相较于红黑树具有更为严厉的自平衡性，因而他在调整二叉树的形状上耗费的功能会更多，并且参阅红黑树的例子，查找id为7和16的比较次数更少，并且没有显着的“右倾”，也便是说，许多的次序刺进不会导致查询功能的下降，这从根本上处理了红黑树的问题。可是AVL树也并不能作为 Mysql 数据库的索引数据结构，由于数据库查询数据的瓶颈在于磁盘 IO，假如运用的是 AVL 树，咱们每一个树节点只存储了一个数据，咱们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里比如查询 id=7 这个数据咱们就要进行磁盘 IO 三次。所以咱们规划数据库索引时需求考虑的问题便是减少磁盘 IO 的次数。
磁盘IO特点
磁盘 IO 有个有个特点，便是从磁盘读取 1B 数据和 1KB 数据所耗费的时刻是根本一样的，咱们能够在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这便是 B 树，B+树的的规划原理了。
B树
假定B 树每个节点约束最多存储两个 key，一个节点假如超过两个 key 就会主动分裂，那么在查询id=7的节点时只需求查询两次就能够得到，优于AVL树。假如每一次尽可能在一次磁盘 IO 中多读一点数据到内存，即每个节点存储的key适当增加，效果是否会更好？答案是必定的。当咱们把单个节点约束的 key 个数设置为 6 之后，一个存储了 7 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次，由此咱们能够考虑B+树。
B+树
B+树与B树的不同在于B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了许多个数据，可是 B+树一个节点能存许多索引，B+树叶子节点存所有的数据，并且B+树的叶子节点是数据阶段用了一个链表串联起来，这就处理了规模查找问题。
挑选B+树的理由
经过以上数据结构的对比，咱们能够得出B+树是最优的作为MySQL底层索引的数据结构，由于B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储许多索引，使得整个 B+树高度下降，减少了磁盘 IO。其次，B+树的叶子节点是真实数据存储的地方，叶子节点用了链表连接起来，这个链表本身便是有序的，在数据规模查找时，更具备功率，因而 B+树在查找功率、规模查找中都有着十分不错的功能。
