杭州网站优化公司,国际网站群建设方案,站长之家产品介绍,网站建设相关职业岗位背景
首先#xff0c;来谈谈B树。为什么要使用B树#xff1f;我们需要明白以下两个事实#xff1a; 【事实1】
不同容量的存储器#xff0c;访问速度差异悬殊。以磁盘和内存为例#xff0c;访问磁盘的时间大概是ms级的#xff0c;访问内存的时间大概是ns级的。有个形象…背景
首先来谈谈B树。为什么要使用B树我们需要明白以下两个事实 【事实1】
不同容量的存储器访问速度差异悬殊。以磁盘和内存为例访问磁盘的时间大概是ms级的访问内存的时间大概是ns级的。有个形象的比喻若一次内存访问需要1秒则一次外存访问需要1天。所以现在的存储系统都是分级组织的。 最常用的数据尽可能放在更高层、更小的存储器中只有在当前层找不到才向更低层、更大的存储器中寻找。这也就解释了当处理大规模数据的时候指无法将数据一次性存入内存算法的实际运行时间往往取决于数据在不同存储级别之间的IO次数。因此要想提升速度关键在于减少IO。 【事实2】
磁盘读取数据是以数据块(block)或者页page为基本单位的位于同一数据块中的所有数据都能被一次性全部读取出来。
换句话说从磁盘中读1B与读1KB几乎一样快因此想要提升速度应该利用外存批量访问的特点在一些文章中也称其为磁盘预读。系统之所以这么设计是基于一个著名的局部性原理 当一个数据被用到时其附近的数据也通常会马上被使用程序运行期间所需要的数据通常比较集中
B树
假设有10亿条记录100010001000如果使用平衡二叉搜索树Balanced Binary Search Tree, BBST最坏的情况下查找需要log(2, 10^9) 30次 I/O 操作且每次只能读出一个关键字即如果这次读出来的关键字不是我要查找的就要再进行一次I/O去读取数据。如果换成B树会是怎样的情况呢
B 树是为了磁盘或其它辅助存储设备而设计的一种多叉平衡搜索树。多级存储系统中使用B树可针对外部查找大大减少I/O次数。通过B树可充分利用外存对批量访问的高效支持将此特点转化为优点。每下降一层都以超级结点为单位超级结点就是指一个结点内包含多个关键字从磁盘中读入一组关键字。那么具体多大为一组呢
一个节点存放多少数据视磁盘的数据块大小而定比如磁盘中1 block的大小有1024KB假设每个关键字的大小为 4 Byte则可设定每一组的大小m 1024 KB / 4 Byte 256。目前多数数据库系统采用 m 200~300。假设取m 256则B树存储1亿条数据的树的高度大概是 log(256, 10^9) 4也就是单次查询所需要进行的I/O次数不超过 4 次由此大大减少了I/O次数。
一般来说B树的根节点常驻于内存中B树的查找过程是这样的首先由于一个节点内包含多个比如是256个关键码所以需要先顺序/二分来查找如果找到则查找成功如果失败则根据相应的引用从磁盘中读入下一层的节点数据这里就涉及到一次磁盘I/O同样的在节点内顺序查找如此往复进行…事实上B树查找所消耗的时间很大一部分花在了I/O上所以减少I/O次数是非常重要的。
B树的定义
B树就是平衡的多路搜索树所谓的m阶B树即m路平衡搜索树。根据维基百科的定义一棵m阶B树需满足以下要求
每个结点至多含有m个分支节点m2。除根结点之外的每个非叶结点至少含有┌m/2┐个分支。若根结点不是叶子结点则至少有2个孩子。一个含有k个孩子的非叶结点包含k-1个关键字。每个结点内的关键字按升序排列所有的叶子结点都出现在同一层。实际上这些结点并不存在可以看作是外部结点。 根据节点的分支的上下限也可以称其为(┌m/2┐, m)树。比如阶数m4时这样的B树也可以称为(2,4)树。事实上(2,4)树是一棵比较特殊的B树它和红黑树有着特别的渊源后面谈及红黑树时会谈到。
并且每个内部结点的关键字都作为其子树的分隔值。比如某结点含有2个关键字假设为a1和a2也就是说该结点含有3个子树。那么最左子树的关键字均小于a1中间子树的关键字介于a1~a2最右子树的关键字均大于a2。 示例一棵3阶的B树是这个样子 B树的高度了解 当树的高度最大时则每个结点含有的关键字数应该尽量少。根据定义根结点至少有2个孩子即1个关键字除根结点之外的非叶结点至少有┌m/2┐个孩子即┌m/2┐-1个关键字为了描述方便这里令p ┌m/2┐。
第1层 1个结点 含1个关键字第2层 2个结点 含2*(p-1)个关键字第3层 2p个结点 含2p*(p-1)^2个关键字…第h层 2p^(h-2)个结点 故总的结点个数n≥ 1(p-1)*[22p2p2…2p(h-2)]≥ 2p^(h-1)-1
从而推导出 h ≤ log_p[(n1)/2] 1 其中p为底数p┌m/2┐ 最小高度 当树的高度最低时则每个结点的关键字都至多含有m个孩子即m-1个关键字则有
n ≤ (m-1)*(1 m m^2 ... m^(h-1)) m^h - 1从而推导出 h ≥ log_m(n1) 其中m为底数
B树
B树的定义 B树是B树的一个变体B树与B树最大的区别在于
叶子结点包含全部关键字以及指向相应记录的指针而且叶结点中的关键字按大小顺序排列相邻叶结点用指针连接。非叶结点仅存储其子树的最大或最小关键字可以看成是索引。 一棵3阶的B树示例好好体会和B树的区别两者的关键字是一样的 问为什么说B树比B树更适合实际应用中操作系统的文件索引和数据库索引 答B树更适合外部存储。由于内结点不存放真正的数据只是存放其子树的最大或最小的关键字作为索引一个结点可以存储更多的关键字每个结点能索引的范围更大更精确也意味着B树单次磁盘IO的信息量大于B树I/O的次数相对减少。MySQL是一种关系型数据库区间访问是常见的一种情况B树叶结点增加的链指针加强了区间访问性可使用在区间查询的场景而使用B树则无法进行区间查找。 出处cnblogs.com/kkbill/p/11381783.html
