这次准备出一个关于B树的合集。在第一部分，先来介绍下B树的基本概念。,B树与bst等二叉树不同，B树是多叉树，而且B树是自平衡树。B树的Search、Insert、Remove算法时间复杂度都是O(log N)。,B树常常用于数据库。数据库常常数据量巨大，因此不可能光放到内存中，需要放到硬盘中进行存储。而硬盘是块设备，就是一次读取一块区域，而B树是多叉树，因此有多个key，所以一块区域就可以包含多个key。另外硬盘相比内存比较慢，B树因为是多叉树相对于二叉树更矮，所以能更多的减少硬盘交互的次数。,B树有一些属性，我更愿意称这些属性为规约或者说规约形成的结果：,
,1、B树用来衡量每个节点(node)的大小的度量衡被称为度(degree，简写为t)和秩(order，简写为m)。度和秩是不同的两个角度，度是说B树的任意节点(除了root节点)至少有t个分叉(至多2t个分叉)，秩是说B树的任意节点(除了root节点)至多有m个分叉。后续将以度为度量衡进行解释B树。,2、因为任意节点(除了root节点)至少有t个分叉，所以任意节点(除了root节点)至少有t-1个key。,3、与2同理，任意节点(除了root节点)至多有2t-1个key。可见是个奇数。,4、任意节点中的key都是按升序排列的。所以可以在节点上方便的使用二分查找。,5、任意两个key k1和k2中间的子树的key都在k1到k2的范围内。如上面的图中所示。,6、Insert只会发生在叶子节点。,7、B树的Search、Insert和Remove，都是从root节点出发的。,8、所有的叶子节点都在同一level。,9、与其他自平衡树一样，B树的Search、Insert、Remove算法时间复杂度都是O(log N)。
文章版权声明
1 原创文章作者：cmcc，如若转载，请注明出处： https://www.52hwl.com/18834.html
2 温馨提示：软件侵权请联系469472785#qq.com（三天内删除相关链接）资源失效请留言反馈
3 下载提示：如遇蓝奏云无法访问，请修改lanzous(把s修改成x)
4 免责声明：本站为个人博客，所有软件信息均来自网络 修改版软件，加群广告提示为修改者自留，非本站信息，注意鉴别
微信扫一扫 
支付宝扫一扫 