B树学习笔记之B树的结构

超、凢脫俗 2022-05-26 06:10 150阅读 0赞

![70][]

*  **每一个节点可有多个分叉**
 *  **所有底层节点的深度完全一致**
 *  **B树矮宽**

**一. 多路平衡**

**1. B树的设计者将其定义为一种平衡的多路（multi-way）搜索树**

**![70 1][]**

**两层两层去考察节点，每一个节点及它的左右孩子合成一个超级节点。**

**二. 还是I/O**

*  **多级存储系统中使用B-树，可针对外部查找，大大减少I/O次数**
 *  **若有n=1G个记录，每次查找需要log(2,2^30)=30次I/O操作，每次只读出一个关键码，得不偿失。若将它们组织为一棵AVL树，高度大致为30层。最坏情况下，单次查找需要深入30层，每一层都需执行一次IO操作。**
 *  **B树会充分利用外存对批量访问的高效支持，将此特点转化为优点。每下降一层，都以超级节点为单位，读入一组关键码。**

![70 2][]**（一节车厢装载若干粉笔）**

**-------------------------------------------------------------------------------------**

**这节车厢要设计成多大?**

**视磁盘的数据块大小而定，m=\#keys/pg。目前多数数据库系统采用m=200~300**

**回到上例，若取m=256=2^8，则每次查找只需log(2^8,2^30)=4次I/O操作。**

**三. 深度统一**

**![70 3][]**

**四. 阶次含义**

**其给出了每个超级节点规模的上限，同时也给出了下限。**

**![70 4][]**

**m=5时（5阶B树），每个节点的分支数不得超过5，同时一般节点所拥有的分支数也不得少于3，可称之为（3,5）树。**

**（节点分支总数超过B的阶次m，称作上溢overflow）**

**五. 紧凑表示**

**![70 5][]**

**对B树的画法做紧凑处理。（注意：图c只是省略了外部节点，不代表没有）**

[70]: /images/20220526/a496e1c69995415b90b5047a325f6b5f.png
[70 1]: /images/20220526/0723108f993946e79bd3c96217ce8926.png
[70 2]: /images/20220526/91207af3a31046d3a380253eaef7fcff.png
[70 3]: /images/20220526/10a5a45ea7264f3e868b2e40c3b50426.png
[70 4]: /images/20220526/a71e808b6cf0492b951d26013c980d87.png
[70 5]: /images/20220526/2809b519aa05464f834f252db0d9eabd.png

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】B树，B+树，B*树

B树的插入，B+树的插入，B*树

桃扇骨/ 2024年04月21日 19:19/ 0 赞/ 51 阅读

相关数据结构之“树”——二叉树、红黑树、B树、B+树、B*树

这篇文章主要简单总结下二叉树、红黑树、B树、B+树、B\树的基本结构和原理。一、二叉树二叉树就是度不超过2的树(每个结点最多有两个子结点)。二叉树是有序树（二

「爱情、让人受尽委屈。」/ 2024年03月22日 15:04/ 0 赞/ 32 阅读

相关数据结构--B 树、B+ 树、B* 树

1. B 树、B+ 树、B\ 树 1.1. 前言 > 前面讨论的二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced BinaryS

た入场券/ 2022年08月20日 04:26/ 0 赞/ 194 阅读

相关数据结构之B-树、B+树

B树的概念是为了解决一些现实问题而提出的，当数据量太大时，而内存中又无法存储这么多的数据，那么就需要将数据存储在磁盘上，如果继续采用平衡树的方法就会带来一些问题，平衡树每个节点

我就是我/ 2022年05月27日 14:09/ 0 赞/ 192 阅读

相关 B树学习笔记之B树的删除

B树的下溢发生于删除关键码后违反了B树的性质。 ![70][] 一. 旋转如果左右兄弟存在，则间接向左右兄弟借关键码 ![70 1][] 二.

分手后的思念是犯贱/ 2022年05月26日 06:29/ 0 赞/ 180 阅读

相关 B树学习笔记之B树的插入

一. 上溢插入新的关键码后违反了B树的性质，称为B树的上溢，此时需做分裂。二. 分裂 1. 中位数 ![70][] 2. ![70 1][] 等效

冷不防/ 2022年05月26日 06:29/ 0 赞/ 136 阅读

相关 B树学习笔记之B树的查找

只载入必需的节点到内存，尽可能减少I/O操作，非必需的存到外存。对于处于活跃状态的B树，根节点常驻于内存每个节点的关键码均已存成向量在存储了n个元

向右看齐/ 2022年05月26日 06:28/ 0 赞/ 132 阅读

相关 B树学习笔记之B树的结构

![70][] 每一个节点可有多个分叉所有底层节点的深度完全一致 B树矮宽一. 多路平衡 1. B树的设计者将其定义为一种平衡的多路（multi-w

超、凢脫俗/ 2022年05月26日 06:10/ 0 赞/ 151 阅读

相关 B树学习笔记之B树的动机

开场白：B树等效于BST。B树最初也是最主要的功能在于弥合不同存储级别之间在访问速度上的巨大差异，实现搞笑的I/O。现实中，内存的容量有限，系统存储容量的增长速度<<应用问

矫情吗；*/ 2022年05月26日 06:06/ 0 赞/ 111 阅读

相关 B树（B-树 B_树）、B+树、B*树

B树 [B-tree][]树即[B树][B]，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实

野性酷女/ 2021年12月23日 02:55/ 0 赞/ 544 阅读