赞
踩
如果能在头脑中构建一幅MySQL各组件之间如何协同工作的架构图,有助于深入理解MySQL服务器。下图展示了MySQL的逻辑架构图。
平衡二叉树首先需要符合二叉查找树的定义,其次必须满足任何节点的两个子树的高度差不能大于1。显然图②不满足平衡二叉树的定义,而图①是一课平衡二叉树。平衡二叉树的查找性能是比较高的(性能最好的是最优二叉树),查询性能越好,维护的成本就越大。比如图①的平衡二叉树,当用户需要插入一个新的值9的节点时,就需要做出如下变动。
通过一次左旋操作就将插入后的树重新变为平衡二叉树是最简单的情况了,实际应用场景中可能需要旋转多次。至此我们可以考虑一个问题,平衡二叉树的查找效率还不错,实现也非常简单,相应的维护成本还能接受,为什么MySQL索引不直接使用平衡二叉树?
一种行之有效的解决方法是减少树的深度,将二叉树变为m叉树(多路搜索树),而B+Tree就是一种多路搜索树。理解B+Tree时,只需要理解其最重要的两个特征即可:第一,所有的关键字(可以理解为数据)都存储在叶子节点(Leaf Page),非叶子节点(Index Page)并不存储真正的数据,所有记录节点都是按键值大小顺序存放在同一层叶子节点上。其次,所有的叶子节点由指针连接。如下图为高度为2的简化了的B+Tree。
仍以上面的树为例,我们假设每个节点只能存储4个内节点。首先要插入第一个节点28,如下图所示。
最后插入一个节点95,这时候Index Page和Leaf Page都满了,就需要做两次拆分,如下图所示。
高性能策略
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。