一文读懂 带你从简单的排序二叉树开始一步步到b+树_二叉树到b+树的演变过程及原因

最普通的二叉树 插入搜索查找都没有明显的优化效率 本文不做讨论 作者默认你已经具有最基础的数据结构知识

为了优化插入搜索删除效率 二叉排序树从此而生 他有什么优势呢 左子结点的key值永远比父节点的key值小 右子结点的key值永远比父节点的key值大 请记住是key值 不是value值  如果key值和value值分不清 那么请去补一下基础 在进行插入搜索删除时 就能通过与父节点的比较 从而确定下一次比较是比较左子节点还是右子节点 虽然他很爽了 但是在某一些情况下 比如你插入顺序是从小到大顺序插入节点 他就变成了一个单链表 如下图所示

明显可以看到 这样与普通单链表没有任何区别 效率极差

在此基础上 人们又想出了一个数据结构 平衡二叉排序树 也称AVL树 他解决了排序树会因为插入情况不同而退化为单链表或者退化为很垃圾的树的问题 为此他引入了两种操作 左旋和右旋 在插入节点后发现本平衡二叉排序树不平衡时(即某一节点左右子树深度之差的绝对值大于1) 他会经过左旋和右旋保持平衡 操作如下 下图引入别人博客的一张图

可以看到平衡二叉排序树可以保证左右子树深度之差不会过于离谱 查找的效率明显会优于普通排序二叉树

旋转分为RR型 RL型 LR型 LL型 具体怎么旋转不在本文讨论范围之内 但是既然这颗AVL树自平衡了 已经这么nice了 为什么还需要红黑树呢？ AVL树好就好在他要求每个节点高度平衡 但是这也是他的缺点 旋转是非常耗时的 频繁插入和删除节点的情况下得不偿失(注意 如果查找是你的数据结构的主要需求的话 AVL树是优于红黑树的)而红黑树不是一颗追求高度平衡的排序树 他允许局部不平衡 只要满足下面五条性质就能称之为红黑树 这时候你就要问为什么满足这五条性质的树插入删除搜索的效率就很快呢？ 本文作者我也不知道 他背后有数学理论的支撑(膜拜大佬) 对于推导过程感兴趣的朋友可以自行谷歌

红黑树性质如下:

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点只能是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。
性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高！

红黑树结构体定义:

 
typedef int KEY_TYPE;
 
typedef struct _rbtree_node {
	unsigned char color;
	struct _rbtree_node *right;
	struct _rbtree_node *left;
	struct _rbtree_node *parent;
	KEY_TYPE key;
	void *value;
} rbtree_node;
 
typedef struct _rbtree {
	rbtree_node *root;
	rbtree_node *nil;
} rbtree;

可以看到啊 红黑树的结点定义比普通的二叉排序树多了一个parent结点 红黑树节点多了一个nil节点 为什么多了一个parent结点呢 因为红黑树的插入 删除是非常麻烦的 他需要频繁的去查询父节点的颜色 和祖父节点的颜色  所以引入一个parent结点很舒服  那为什么有一个nil结点呢 因为默认所有叶子节点为黑而且隐藏 只要指向nil我就默认你是叶子节点且黑色

具体红黑树的插入删除算法可以去看我上一篇文章 连接如下

红黑树的插入 删除以及左旋和右旋和搜索_杀神李的博客-CSDN博客

那么聪明的读者这时候又要问了 既然红黑树都这么牛逼了 为什么还有B树(B-树就是B树) B+树呢

那么请思考一个问题 我能把一颗树的所有节点都放在内存中嘛？ 我内存大小为多少 4G？8G？16G？32G？  个人数据可能勉强还够用 但是海量上T的数据呢？ 你内存能够把全部结点和数据都存储在内存嘛？明显是无稽之谈 所以大部分数据还是存储在磁盘 但是存储在磁盘就会有一个大问题了  你红黑树深度过高之后 底部很多结点都放在磁盘 在磁盘中取到下一个结点的位置之后还要去磁盘拿数据 要频繁的去磁盘取数据 磁盘取数据有多慢? 相信读者也知道 

请思考红黑树最大的缺点是啥？ 没错 红黑树最大的缺点就是他是一颗二叉树  他规定了一棵树只能有两个子节点 那么当数据量大起来的时候 无可避免的就会造成树的深度过大 从而多次进行IO操作

那么有没有一种数据结构能够让我们减少去磁盘寻找数据的次数呢? 经过大佬们多年的 研究 B树横空出世 他最大的优点就是深度不会很大 并且是一个多叉树   让我们来看看简单的一颗B树

可以看到他是三叉的并且层数只有三层 但是他却存储了22个value 试问红黑树存储22个value需要 几层呢？  层数小了那么去磁盘拿数据的次数是不是就小了呢 那么效率是不是就提高了呢？

那么B树现在看起来似乎已经是完美的了 既减少了IO的次数 效率还高 为什么还要有B+树呢 

为了引入B+树 问读者们一个问题 假如B树一个结点为4KB 内存4G 你能放在内存中的结点为多少呢？ 1024*1024个吧 那么再问读者们一个问题 一个结点中key值占了多少大小 value值又占了多少大小呢 可能value值就占用了3KB 但是key值只占用了1KB 既然key值只占用了1KB 那么我的下一层结点的个数是不是就少了呢 假如key值用int型存储 1KB那么key值就有256个 那么我是不是最多只能开257叉  下一层是不是就最多只有257个结点了呢 (如果这句话看不懂 请看上图根结点 key值只有两个 但是叉数却有3 自己多想想 下文不再做解释) 那既然开的叉少了 那么我能存储的总数据是不是就少了呢?

那么聪明的读者这时候就想到了 既然如此 我为了在有限的层数里多存一点数据 那么我就需要多开几叉 让key值填满我的结点不就好了嘛？ 是的 事实上B+树也是这么做的 除了叶子节点会存储数据以外 所有节点只存储key值 

如果不存储数据，那么就会存储更多的键值，相应的树的叉数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。

注意啊 上图中除了叶子节点之外的节点都只存储了key值  

读完本文 再去了解InnoDB引擎原理的文章便会事半功倍