Nemo的轨迹

work hard, be persistent, and good luck

0%

Mysql笔记:从 BST 到 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-树定义如下:

  • 根节点至少两个孩子

  • 每一个中间的节点,包含 k-1 个元素和 k 个孩子( m/2 <= k <= m )

  • 叶子节点都位于同一层,且都包含 k-1 个元素( m/2 <= k <= m )

  • 每一个节点元素都是从小到大排序,每个节点第 k-1 个元素是第k 个孩子的值域切分点

B+树: 为什么 B-树还不够好

所谓性能压榨,没有最好,只有更好…

B+树三个特征:

  1. 有k个子树的中间节点包含有k个元素,每个元素不保存数据,只用来当索引

  2. 所有的叶子结点中包含了全部元素的信息,同时数据也都保存在叶子节点

  3. 中间节点的元素同时也存在与子节点,是子节点中的极值(极大/极小)

B+树优于 B- 树的三个点:

  1. B+树更加”矮胖”

B-树 中间节点有实际数据的地址信息;B+树中间节点只有索引,没有任何数据关联,实际数据的地址信息都可以在叶子中找到 (特征2).这样的好处是,每一次 page 加载的更多节点元素

  1. 查询稳定

最好最坏的查询都要到叶子节点(数据都放在叶子节点),查询性能是稳定的.

  1. 范围查询方便

所有的叶子节点按迅速形成了一个链表.在范围查询中(体现了实用主义:数据库经常要范围查询) ,B+树只要找到两端的叶子,叶子节点之间的数据都是可遍历的. B- 树因为数据可能在中间节点,也可能在叶子节点,导致要一个个查询.

一图胜前言: B-树 Vs B+树

补充阅读

漫画算法这几篇总结得比我这篇要好:

漫画算法:什么是红黑树?

漫画算法:什么是 B 树?

漫画算法:什么是 B+ 树?

MySQL索引背后的数据结构及算法原理: 写得十分好的一篇文章,图文并茂.