Mysql笔记:从 BST 到 B+树

发表于 2018-02-24 分类于 ToolorToy Disqus：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

mysql这样的关系型数据库,当你深入了解,一定绕不开它的底层存储方式: B+树.梳理一下整个发展逻辑.本篇目的在于让你理解这一数据结构

BST( 二叉查找树) –> AVL(平衡二叉树) –> B-树 –> B+树

背景知识:

单机性能瓶颈往往来自于: CPU 和磁盘IO. 而数据库存取是典型的磁盘 IO 密集型任务.
数据库的最重要的一个优化点就是: 尽可能减少磁盘 IO

来自二分查找的启示: BST

想要高效查找,那还不简单,借用二分查找的思想

定义:

二叉查找树首先是一颗二叉树(每个节点最多两个儿子)
对树的每个节点X: 左子树的所有节点的值都小于 X的值, 右子树所有节点的值都大于 X 的值

BST 的思想来自于二分查找: 每一次我把要查找的数据量减半,这比我从头到尾遍历高效.
但 BST 会有退化的风险: 如图,在这样的情况下,

BST+强制平衡= AVL

发现坑了怎么办,填呗.既然是高度引起的问题,我们在 BST 基础上强化一下条件:

对树的任一节点 X: X左子树的高度和右子树的高度差不大于1

这样带来的一个问题是: 每次我们对节点的改动( insert 或者 Delete ), 都要判断是否违法了高度差不能超过1的限制,超过了,我们需要做额外的工作:旋转.

旋转分:单旋转, 双旋转,这里不展开了,因为网上一查一大把.

当平衡可以稍微放宽一些:RBT红黑树

填了一个坑,又多了一个坑

红黑树的性质: 最长路径长度不超过最短路径长度的2倍.这句话怎么理解?

首先AVL 有什么问题呢? 分个方面来思考:

查找: 没问题,高度的限制保证了查找的最坏的情况是 lg(N),也就是说,它的查找效率是稳定的.
插入: 每插入一个节点最多旋转一次(单旋转或者双旋转). 旋转其实是指针指向的变动,而这个是常数级别,查找插入的位置是 lg(N) ,总体时间 lg(N)
删除: 删除需要检查删除节点到根节点所有节点的平衡因子. 找到删除的节点 lg(N), 路径上最多会有 lg(N) 次旋转.所以删除的时间是 O(2lgN)

所以删除的代价会更大. 问题出在删除节点到根节点的路径长度上.这时候要是对强制平衡稍微放宽一些: 不要求每一个节点都平衡,这样使得旋转次数减少.

下面是 RBT 的定义,直接记忆会把人懵掉了(反正我第一次看是懵了),记住这句话:”最长路径长度不超过最短路径长度的2倍”,下面的性质都是为了保证这一点.这样会更好.

首先是一个 BST 树
每一个节点要么是红色,要么是黑色
根节点使黑色
叶子节点都是黑色的 NULL 节点
每个红色节点的两个子节点都是黑色( 不会连续出现两个红节点 )
从任一节点出发,到叶子节点的所有路径中,都有相同数目的黑色节点

RBT 保证了:

删除一个节点最多需要3次旋转(不需要严格平衡)

天下没有白吃的午餐,付出的代价是(相比 AVL):

查找: 基本维持在 lg(N), 但在最坏情况下比 AVL 差(最长路径是最短路径的2倍少1 )
插入: 插入节点最多需要2次旋转

到正题了:那为什么数据库不用 RBT

这里我按我的理解来说:

** B-树比 RBT “矮胖”是它的外在表现方式. 本质是 B-树在每一个节点提供了更多的信息,使得磁盘加载的数据量减少更多 **

当把数据加载到内存,RBT每一个节点都是固定的值,要是查找的值不在其中,最坏情况我们需要不断加载数据.(这里消耗的可是磁盘IO 呀)
B- 树每一个节点其实是一个区间值,也就是说,它包含了更多的信息: 当目标值不在这个区间,这个区间的数据我们都可以剔除(也就是说不用加载了,磁盘 IO 就节约下来了).
RBT剔除的是当前值, B-树剔除的是整个区间.后者效率高.

提问: B-树每一个节点都是一个区间,也就是说目标值对一个节点都需要两次判断, RBT 只需要一次,这样的损耗怎么不考虑进去?
回答: 因为比较是在内存中. 内存操作速度可以认为远快于磁盘 IO.

让一个节点包含更多孩子可以减少磁盘 IO,同时我们也希望 RBT 的大部分性质可以保留:lg级别的查增删操作,于是有了 B- 树.一个 m 阶的 B-树定义如下: