济南网站建设公司大全,内蒙古建设厅安全资料网站,wap网站开发需要多少钱,网站被攻击怎么让百度重新蜘蛛自动抓文章目录搜索结构B树B树的插入B树的遍历B树的性能B树B树的插入B树的遍历B*树B*树的插入总结搜索结构
如果我们有大量的数据需要永久存储#xff0c;就需要存储到硬盘之中。但是硬盘的访问速度远远小于内存#xff0c;并且由于数据量过大#xff0c;无法一次性加载到内存中。…
文章目录搜索结构B树B树的插入B树的遍历B树的性能B树B树的插入B树的遍历B*树B*树的插入总结搜索结构
如果我们有大量的数据需要永久存储就需要存储到硬盘之中。但是硬盘的访问速度远远小于内存并且由于数据量过大无法一次性加载到内存中。
此时就可以考虑将数据存储在硬盘中而数据的地址则加载到内存中通过某种搜索结构进行存储使用时只需要通过该结构查找到地址在通过地址去找到对应的数据即可。
常用的几种搜索结构二叉搜索树、AVL树、红黑树、哈希、位图、布隆过滤器。
考虑到查找性能以及内存消耗其中适合这种场景的只有平衡二叉搜索树AVL、红黑树。 但即使平衡二叉搜索树的搜索性能能达到 O(log2N)由于数据量过于庞大例如存储了 10亿个数则可能最多需要查找 30次。这个数字看起来不是很多因为之前我们比较的是内存的速度即使是 10亿个数 也能一瞬间查找完。但是对于硬盘来说由于硬盘的速率低每一次 IO 都意味这大量的损耗所以这种方法也不太合适。
如果想要提高查找的效率那么唯一的方法就是压缩树的高度而压缩的方法就是将二叉树变为 M叉树也就是使用到 M路平衡搜索树——B树。 B树
B树 即一棵平衡的 M路平衡搜索树M 2可以是 空树 或者满足以下性质
根节点至少有 2 个孩子、最多有 M 个孩子除根结点外的非叶节点有 i 个孩子 M/2(上取整) i M每个非叶节点有 j 个关键字 M/2-1(上取整) j M-1 并且以升序排列key[i] 和 key[i1] 之间的孩子节点的值介于 key[i]、key[i1] 之间所有的叶子节点都在同一层。
对照一棵 M3 的 B树 来理解
节点实现
templateclass K, int M 3
struct BTreeNode
{K _keys[M]; // 存放元素BTreeNodeK, M* _pSub[M1]; // 存放孩子节点注意孩子比数据多一个BTreeNodeK, M* _pParent; // 在分裂节点后可能需要继续向上插入为实现简单增加parent域size_t _size; // 节点中有效元素的个数BTreeNode(): _pParent(NULL), _size(0){for(size_t i 0; i M; i)_pSub[i] NULL;}
};B树的插入
下面拿一个 M3 的 三叉B树 来举例子。PS三叉树即每个节点至多 3 个孩子2 个 keykey 的数量永远比孩子少一个
假设使用以下数据构建B树 {63, 131, 85, 39, 148, 31, 111}B树从叶子节点的位置进行插入 首先依次插入前三个节点当插入到第三个时由于三叉树的 key 只能有 2 个所以此时会采取分裂的方法来维持树的平衡。
B树分裂的规则是创建一个兄弟节点拷贝右半区间的数据到兄弟节点左半区间保留中位数放到父亲节点如果没有则创建新的根节点。
B树 与 AVL 的旋转、红黑树的旋转变色不一样它使用了分裂的方法来维持树的平衡这样的好处是既能做到平衡也保证了非根节点至少有一半的空间利用率。
所以此时按照上面的规则进行分裂
接着插入 39148 然后插入 31开始分裂 接着插入111此时再次发生分裂 此时可以看到叶子节点已经分裂成了 4 个并且根节点的 key 也达到了 3 个不符合 B树 的性质每个根节点最多有 M 个孩子、M - 1 个key因此继续分裂 此时树重新平衡。从上面可以看出来本质上B树的设计还是参考了二叉搜索树。 B树的遍历
B树的有序遍历还是通过中序遍历来完成不过需要通过队列或者递归遍历完这个节点的所有的key。
void _InOrder(PNode pRoot)
{if(NULL pRoot)return;for(size_t i 0; i pRoot-_size; i){_InOrder(pRoot-_pSub[i]);cout pRoot-_keys[i] ;}_InOrder(pRoot-_pSub[pRoot-_size]);
}B树的性能
作为一个M路平衡搜索树B树的搜索性能达到了 logM1N\log_{M1}NlogM1N ~ logM/2N\log_{M/2}NlogM/2N 之间查找到指定关键字的方法是
在根结点所包含的关键字 K1、…、Kn 查找给定的关键字可用顺序查找或二分查找法若找到等于给定值的关键字则查找成功否则一定可以确定要查找的关键字在 Ki 与 Ki1之间Pi 为指向子树根节点的指针此时取指针 Pi 所指的结点继续查找直至找到或指针 Pi 为空 时查找失败。
比起二叉平衡搜索树速度快了一大截并且大大的减少了硬盘 IO 的次数所以在文件系统以及数据库索引等方面使用的都是这种数据结构。 B树
B树是B树的变形主要性质如下
其定义基本与B树相同非叶子节点的 孩子 与 key 个数相同简化规则非叶子节点由叶子节点的最小值构成充当索引所以不可能在非叶子节点命中所有数据都出现在叶子节点并且所有叶子节点都链接起来同时是有序的。方便遍历 B树的插入
这里为了方便使用 三阶B树 举例子这里还是使用同样的数据。{63, 131, 85, 39, 148, 31, 111}
首先插入 63并把 63 作为父节点的索引:
接着插入 13185 : 当插入 39 时发生分裂分裂规则与之前略有区别。
B树的分裂规则因为此时父节点存储的是索引所以此时只会将左半部分数据保留右半部分数据放入新建的兄弟节点并且会向上更新父节点的索引。 当插入 111 时发生分裂 B树的遍历
从上面可以看出来B树的主要特点其实就是更方便进行遍历因为其将所有数据存储在叶子节点所有非叶子节点就相当于一个索引。其所有叶子节点连接起来像遍历链表一样遍历B树。这样的结构使得B树的查找相当于对关键字全集做一次二分查找。
所以通常文件的索引系统都会采用B树的结构。 B*树
B*树则又是对B树的变形其性质如下
其定义基本与B树相同将非叶子节点也连接起来分裂方式再次修改保证每个节点中 key 的数量 [2/3 * MM]提高空间利用率从1/2提升到了2/3 B*树的插入
B*树再次修改了插入规则规则修改为
如果当前节点数据已满而兄弟节点未满则将数据放入兄弟节点而当两个节点都满了之后再进行分裂分裂时在原节点与兄弟节点之间创建新节点从两个节点分别取出 1/3 的数据放入新创建的结点。
还是原来那些数据 {63, 131, 85, 39, 148, 31, 111} :
接下来插入 39
插入 148、31 此时插入111发生分裂从两边各取走 1/3 的数据
从上面可以看出B*树的最大改进就是将B树的空间利用率从1/2提升到了2/3并且对非叶子节点也进行了连接查找更加便利。 总结
