《MySQL实战45讲》学习笔记3——InnoDB为什么采用B+树结构实现索引

索引的作用是提高查询效率，其实现方式有很多种，常见的索引模型有哈希表、有序列表、搜索树等。

哈希表

• 一种以key-value键值对的方式存储数据的结构，通过指定的key可以找到对应的value。
• 哈希把值放在数组里，用一个哈希函数把key换算成一个确定位置，然后把value放在数组的这个位置。但是，多个key值经过哈希函数的换算，可能会出现同一个值，即哈希冲突，常见的解决办法是链地址法，即将所有的相同Hash值的key放在一个链表中，这样，无论有多少个冲突，都只是在当前位置给单链表增加节点。
• 适用于只有等值查询的场景，区间查询会很慢。

有序列表

• 支持等值查询和范围查询，但是更新数据的成本比较高。
• 适用于静态存储索引，比如保存的是2017年某个城市人口信息这类不会修改的数据。

树

1.二叉树：

• 每个节点的左儿子小于父节点，父节点小于右儿子。
• 查找、更新某个节点的时间复杂度都是O(log(N))，搜索效率最高。

2.B树（多叉树）：

根节点至少有两个子节点，每个节点的子节点间，其大小都是从左到右递增。

3.B+树：

• B+树的叶子节点保存了父节点的所有键值和键值对应的数据，每个叶子节点的键值从小到大链接，但非叶子节点不保存键值对应的数据，这样使得B+树每个节点所能保存的键值大大增加；
• 由于B+树的非叶子节点只进行数据索引，不会存实际的键值对应的数据，所有的数据必须到叶子节点才能获取到，所以每次数据查询的次数都一样。

因为索引不止存在内存中，还要写在磁盘上，为了尽量少地读写磁盘，减少IO次数，所以尽管二叉树的效率很高，大多数数据库不会选择二叉树。

可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间。

InnoDB使用B+树索引模型，所有数据都存储在B+树中，每一个索引对应一棵B+树。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

结论：InnoDB采用B+树结构，是因为B+树能够很好地配合磁盘的读写特性，减少单次查询的磁盘访问次数，降低IO、提升性能。

《MySQL实战45讲》学习笔记3——InnoDB为什么采用B+树结构实现索引

原文：https://www.cnblogs.com/sunshineliulu/p/11516851.html