圣弓 网站建设,郑州百度分公司,软件人力外包,做装修哪个网站推广好1 B树介绍
B树#xff08;英语#xff1a;B-tree#xff09;#xff0c;是一种在计算机科学自平衡的树#xff0c;能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作#xff0c;都在对数时间内完成。B树#xff0c;概括来说是一个一般化的…1 B树介绍
B树英语B-tree是一种在计算机科学自平衡的树能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作都在对数时间内完成。B树概括来说是一个一般化的二叉搜索树binary search tree一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同B树适用于读写相对大的数据块的存储系统例如磁盘。B树减少定位记录时所经历的中间过程从而加快访问速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
那为什么要使用 B-树呢或者说为啥要有 B-树呢
要解释清楚这一点我们假设我们的数据量达到了亿级别主存当中根本存储不下我们只能以块的形式从磁盘读取数据与主存的访问时间相比磁盘的 I/O 操作相当耗时而提出 B-树的主要目的就是减少磁盘的 I/O 操作。大多数平衡树的操作查找、插入、删除最大值、最小值等等需要 O(ℎ) 次磁盘访问操作其中 ℎ 是树的高度。但是对于 B-树而言树的高度将不再是logn(其中 n是树中的结点个数而是一个我们可控的高度 ℎ 通过调整 B-树中结点所包含的键【你也可以叫做数据库中的索引本质上就是在磁盘上的一个位置信息】的数目使得 B-树的高度保持一个较小的值。一般而言B-树的结点所包含的键的数目和磁盘块大小一样从数个到数千个不等。由于B-树的高度 h 可控一般远小于logn 所以与 AVL 树和红黑树相比B-树的磁盘访问时间将极大地降低。
平衡二叉排序树是利用插入的成本缓解查找效率----------红黑树来解决最长子树不超过最短子树的2倍。数据量大的时候树会很深查找次数变多-----------B树多叉多路查找树
动画显示树调整的网站Data Structure Visualization
2 B树特点
B树是一种平衡的多叉树通常我们说m阶的B树它必须满足如下条件
每个节点最多有m个子节点。每一个非叶子节点除根节点最少有[m/2]个子节点。如果根节点不是叶子节点那么它至少有两个子节点。有k个子节点的非叶子节点拥有k-1个键且升序排列满足k[i] k[i 1]每个节点至多包含2*k-1个键。所有的叶子节点都在同一层。每个节点的结构是 其中
n记录这个节点关键字的个数
P0存储的是第一个孩子的地址P1存储的是第二个孩子的地址以此类推。。。。。。
K1是第一个关键字K2是第二个关键字以此类推。。。。。。
B树中一个节点的子节点数目的最大值用m表示假如最大值为4则为4阶如下图 性质 每个节点最多有m个子节点。每一个非叶子节点除根节点最少有[m/2]个子节点。如果根节点不是叶子节点那么它至少有两个子节点。有k个子节点的非叶子节点拥有k-1个键且升序排列满足k[i] k[i 1]每个节点至多包含2*k-1个键。所有的叶子节点都在同一层。满足n叉排序树 3 B树的增删改查
磁盘预读
内存跟磁盘发生数据交互的时候一般情况下有一个最小的逻辑单元称之为页,datapage
页一般由操作系统决定是多大一般是4k或者8k我们在数据交互时可以取页的整数倍来进行读取。
电脑的文件都是datapage的整数倍
每个节点放在磁盘块里用B树做索引这个磁盘大小是16k 三层数据。
对比B树和B树 有一个很重要的不同是B树的数据都存在叶子节点上。 参考
[1] https://zh.wikipedia.org/zh-hans/B%E6%A0%91
[2] 图解什么是B树心中有 B 树做人要虚心一文读懂B-树 - 知乎 (zhihu.com)
[3] B 树 - OI Wiki (oi-wiki.org)
[4] 终于把B树搞明白了(四)_B树的删除操作_哔哩哔哩_bilibili
[5] notes/docs/B树和B树详解.md at master · wardseptember/notes · GitHub
