MySQL和B树的那些事
零、铺垫 在介绍B树之前,先来看另一棵神奇的树——二叉排序树(Binary Sort Tree),首先它是一棵树,“二叉”这个描述已经很明显了,就是树上的一根树枝开两个叉,于是递归下来就是二叉树了(下图所示),而这棵树上的节点是已经排好序的,具体的排序规则如下: 若左子树不空,则左子树上所有节点的值均小于它的根节点的值 若右子树不空,则右字数上所有节点的值均大于它的根节点的值 它的左、右子树也分别为二叉排序数(递归定义) 从图中可以看出,二叉排序树组织数据时,