看这篇就够了！MySQL 索引知识点超全总结( 二 ) _MySQL

有序数组数组是在任何一本数据结构和算法的书籍都会介绍到的一种重要的数据结构。有序数组如其字面意思，以 Key 的递增顺序保存数据在数组中。非常适合等值查询和范围查询。
ID：1ID：2......ID:N
在 ID 值没有重复的情况下，上述数组按照 ID 的递增顺序进行保存。这个时候如果需要查询特定 ID 值的 name，用二分法就可以快速得到，时间复杂度是 O(logn) 。
// 二分查找递归实现方式int binary_search(const int arr[], int start, int end, int key){if (start > end)return -1;int mid = start + (end - start) / 2;if (arr[mid] > key)return binary_search(arr, start, mid - 1, key);else if (arr[mid] < key)return binary_search(arr, mid + 1, end, key);elsereturn mid;}有序数组的优点很明显，同样其缺点也很明显。其只适合静态数据，如遇到有数据新增插入，则就会需要数据移动（新申请空间、拷贝数据和释放空间等动作），这将非常消耗资源。
Hash哈希表是一种以键-值（K-V）存储数据的结构，我们只需要输入键 K，就可以找到对应的值 V 。哈希的思路是用特定的哈希函数将 K 换算到数组中的位置，然后将值 V 放到数组的这个位置。如果遇到不同的 K 计算出相同的位置，则在这个位置拉出一个链表依次存放。哈希表适用于等值查询的场景，对应范围查询则无能为力。

文章插图

二叉搜索树二叉搜索树，也称为二叉查找树、有序二叉树或排序二叉树，是指一颗空树或者具有以下性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；

文章插图

二叉搜索树相比于其它数据结构的优势在于查找、插入的时间复杂度较低，为 O(logn) 。为了维持 O(logn)的查询复杂度，需要保持这棵树是平衡二叉树。
二叉搜索树的查找算法：

若 b 是空树，则搜索失败，否则：
若 x 等于 b 的根节点的值，则查找成功；否则：
若 x 小于 b 的根节点的值，则搜索左子树；否则：
查找右子树。

相对于有序数组和 Hash，二叉搜索树在查找和插入两端的表现都非常不错。后续基于此不断的优化，发展出 N 叉树等。
B+树Innodb 存储引擎支持 B+树索引、全文索引和哈希索引。其中 Innodb 存储引擎支持的哈希索引是自适应的，Innodb 存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预。B+树索引是关系型数据库中最常见的一种索引，也将是本文的主角。
数据结构
在前文简单介绍了有序数组和二叉搜索树，对二分查找法和二叉树有了基本了解。B+树的定义相对复杂，在理解索引工作机制上无须深入、只需理解数据组织形式和查找算法即可。我们可以简单的认为 B+树是一种 N 叉树和有序数组的结合体。
例如：

文章插图

B+树的 3 个优点:

层级更低，IO 次数更少
每次都需要查询到叶子节点，查询性能稳定
叶子节点形成有序链表，范围查询方便

操作算法

查找

由根节点自顶向下遍历树，根据分离值在要查找的一边的指针；在节点内使用二分查找来确定位置。

插入

Leaf Page（叶子）满Index Page（索引）满操作

文章插图

删除

叶子节点小于填充因子中间节点小于填充因子操作

文章插图

注：插入和删除两个表格内容来自《MySQL 技术内幕-InnoDB 存储引擎》
填充因子（innodb_fill_factor）：索引构建期间填充的每个 B-tree 页面上的空间百分比，其余空间保留给未来索引增长。从插入和删除操作中可以看到填充因子的值会影响到数据页的 split 和 merge 的频率。将值设置小些，可以减少 split 和 merge 的频率，但是索引相对会占用更多的磁盘空间；反之，则会增加 split 和 merge 的频率，但是可以减少占用磁盘空间。Innodb 对于聚集索引默认会预留 1/16 的空间保证后续的插入和升级索引。