mysql 为什么最终选择了b+ 树

r囧r小猫 2022-10-06 14:54 131阅读 0赞

### 1.MySQL的底层数据结构是 B+ 树，为什么会选择B+ 树呢？ ###

而不是 链表、hash表、红黑树、B树 这些数据结构呢？

*  **链表**：链表的随机读的时间复杂度是 O(n) ，不支持范围查询，当遇到范围查询时，只能一个一个的去遍历。
 *  **hash表**：
    
    1.  要想使时间复杂度保持在 O(1)，就需要优秀的 hash 算法，让数据均匀分布在散列表中。
    2.  因为数据在散列表中是均匀分布的，所以没有顺序，即 hash 表不支持范围查询。
    3.  hash表需要大量的内存空间，将索引全部都加载到内存中。
 *  **红黑树**：
    
    这里要稍稍、简单些一些“历史”。链表只能从头到尾一个个遍历，所以其查询复杂度是O(n)。构建二叉搜索树树(Binary Search Tree，BST) 可以采用二分查找，将查询的时间复杂度降到O(log2n)，但是当有序元素依次插入时构建的二叉树是个链表（层高太高），此时有增加了查找的时间复杂度。
    
    因此出现了**平衡二叉树（AVL）**，它采用左旋和右旋的方式，保证左右子树的高度差不得超过1，从而维持树的查找时间复杂度是O(log2n)，即便是有序元素顺序插入，也能保证时间复杂度不变。但是它有两个缺点：
    
    1.  频繁的左旋和右旋 很耗费性能。
    2.  当数据量很大时，平衡二叉树的层高也是很高的，单次查询可能会很深。
    
    **红黑树**是带有颜色属性的二叉查找树，它只保证黑色平衡，从而减少了左旋和右旋的次数。因为其依旧是二叉树，所以数据量很大时，树层依旧很高。
 *  **B 树**：
    
    怎么样才能降低层高呢？当每个节点可拥有的子节点个数越多，每一层存储的元素就越多，总元素个数一定时，树的层高就越小。B树 是多叉树，也叫平衡多路查找树。每个节点拥有大于两个子结点，所以它比二叉树的层高要低很多。**（红黑树本质上是 2-3-4树，2-3-4 是四阶B树）**
    
    B 树是平衡的、层高也很低。它的每个节点都包含有指针域和数据域(key和data)。因为非叶子节点中存储了数据，所以非叶子节点中存储的索引个数很少，这样导致当树的层高相同的情况下，整棵树能表示的数据的范围有限。所以 B 很好，但不是最优的。
 *  **B+ 树：**
    
    与 B 树不同的是 B+ 树的非叶子节点值存储索引，所有的数据均存储在叶子节点上。而且在叶子节点一层，除最右边的元素以外，所有的叶子节点都有指针指向它右边的节点。
    
    **B树比 B+ 树的优点**：
    
    1.  B+ 树非叶子节点只存储索引，则每个非叶子节点上可以存储更多的索引。树的层高相同时，B+ 树能表示更大的数据范围。
    2.  B+ 树的叶子节点上，处最右的节点外，其余节点均有指针指向它右边的节点，也就是说，B+ 树在叶子节点上可以直接执行范围访问。不用再向 B 树一样执行“左中右”访问整棵树。
    3.  B+ 树的数据全部存放在叶子叶子节点上，表示查找任何值，访问的树的层高是一样的。查询稳定。

### 2.为什么高度为3的B+树存储千万级数据？ ###

解释这个问题的前提，mysql使用InnoDB引擎，mysql默认页文件大小为16k。

假设我们一行数据大小为1k，那么一页存储16条数据，也就是说一个叶子节点能存储16条数据

再来看看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在InnoDB引擎中的大小为6B，一共14B，那么一页中可以存放16k/14B=1170个(主键+指针)

也就是说高度为2的B+树可以存储的数据为:1170*16=18720条；高度为3的B+树可以存储的数据为:1170*1170\*16=21902400(千万条数据)