河南建设工程造价管理协会网站,698元网站建设,公主岭网站建设,施工企业资质等级划分目录 1、介绍
2、B树特征
3、插入
4、删除
5、存储记录
1#xff09;方法1#xff1a;按值存储
2#xff09;方法2#xff1a;按引用存储
3#xff09;方法3#xff1a;按引用列表存储
6、聚类#xff08;Clustering#xff09;
1#xff09;非聚类#xff…目录 1、介绍
2、B树特征
3、插入
4、删除
5、存储记录
1方法1按值存储
2方法2按引用存储
3方法3按引用列表存储
6、聚类Clustering
1非聚类Unclustered
2Clustered
7、计算 I/O 次数
8、批量加载 1、介绍
在之前我们讨论了不同的文件和记录表示方法用于数据存储。本文将介绍索引它是在数据文件之上运行的一种数据结构有助于加速对特定键的读取。
我们可以将数据文件视为书籍的实际内容将索引视为用于快速查找的目录。我们使用索引来使查询运行更快特别是那些经常运行的查询。
考虑一个Web应用程序在登录过程中根据用户名查找 Users 表中用户的记录。在用户名列上建立索引将通过快速找到尝试登录的用户的行来加速登录过程。
学习B树一种特定类型的索引。以下是B树的一个示例 2、B树特征
数字 d 是 B 树的阶数。每个节点除了根节点的条目数量必须满足 d ≤ x ≤ 2d假设没有删除操作发生如果删除数据则叶节点最终可能少于 d 个条目。每个节点内的条目必须排序。在每个内部节点的条目之间有一个指向子节点的指针。由于一个节点最多有 2d 个条目内部节点最多可能有 2d1 个子指针。这也被称为树的扇出度tree’s fanout。位于一个内部节点条目左侧的子节点的键必须小于该条目而位于右侧的子节点的键必须大于或等于该条目。所有叶节点都具有相同的深度并且具有 d 到 2d 个条目即至少半满。
例如这是一颗阶数 d2 的树的节点 请注意该节点满足阶数要求也称为the occupancy invariant 占用不变式d ≤ x ≤ 2d因为在这里 d2而该节点有 3 个条目满足 2 ≤ x ≤ 4。
由于排序和子节点的属性我们可以沿着树向下遍历到叶节点以找到我们需要的记录。这类似于二叉搜索树BSTs。每个从根到叶子的路径具有相同数量的边 - 这就是树的高度。从这个意义上说B树始终是平衡的。换句话说只有具有根节点的B树的高度为0。只有叶节点包含记录或记录的指针 - 这将在后面解释。内部节点非叶节点不包含实际的记录。
例如这是一颗阶数 d1 的树 3、插入
将条目节点插入 B 树可按照以下步骤进行 a. 找到要插入值的叶节点 L。您可以通过沿树向下遍历来完成。按顺序将键和记录添加到叶节点。 b. 如果 L 溢出即 L 有超过 2d 个条目 将其分为 L_1 和 L_2。在 L_1 中保留 d 个条目这意味着 d1 个条目将放在 L_2 中。如果 L 是叶节点将 L_2 的第一个条目复制到父节点。如果 L 不是叶节点则将 L_2 的第一个条目移动到父节点。调整指针。 c. 如果父节点溢出那么对其进行递归即对父节点执行步骤 2。这是唯一会增加树高度的情况 注意我们想要将叶节点数据复制到父节点这样我们就不会丢失叶节点中的数据。请记住建立索引的表中的每个键都必须在叶节点中在内部节点中的键并不意味着该键实际上仍然存在于表中。另一方面我们可以将内部节点数据移动到父节点因为内部节点并不包含实际的数据它们只是在遍历树时引导搜索的引用。
让我们通过一个例子来更好地理解这个过程我们从以下的阶数为 d1 的树开始 让我们将 19 插入到我们的树中。当我们插入 19 时我们看到在具有 17 的叶节点中有空间 现在让我们将 21 插入到我们的树中。当我们插入 21 时它导致一个叶节点溢出。因此我们将这个叶节点分割成两个如下所示的叶节点 L_1 是具有 17 的叶节点而 L_2 是具有 19 和 21 的叶节点。
由于我们分割了一个叶节点我们将 L_2 的第一个条目复制到父节点并调整指针。我们还对父节点的条目进行排序得到 让我们再进行一次插入。这次我们将插入 36。当我们插入 36 时叶节点溢出因此我们将执行与插入 21 时相同的过程得到 请注意现在父节点溢出了因此我们现在必须进行递归。我们将分割父节点得到 L_1 是具有 19 的内部节点而 L_2 是具有 27 和 32 的内部节点。
由于溢出的是内部节点我们将 L_2 的第一个条目移动到父节点并调整指针得到 最后以下是关于插入B树的一些建议说明
通常B 树节点具有至少 d 个条目和最多 2d 个条目。换句话说如果树中的节点在插入之前满足这个不变性通常会满足那么插入后它们将继续满足这个不变性。
当节点包含超过 2d 个条目时发生插入溢出。
4、删除
要删除一个值只需找到适当的叶节点并从该叶节点中删除不需要的值。就是这么简单。是的从技术上讲我们可能会违反一些 B 树的不变性。这没关系因为在实践中我们进行的插入比删除多得多因此删除的内容很快就会被替换。
提醒我们永远不会删除内部节点的键因为它们只用于搜索而不是保存数据。
5、存储记录
直到现在我们还没有讨论过记录实际上是如何存储在叶节点中的。现在让我们来看看。有三种在叶节点中存储记录的方法
1方法1按值存储
在方法1中叶子页面就是数据页面。与其包含指向记录的指针不如说叶子页面包含记录本身。 虽然方法 1 是可能最简单的实现方式但它有一个重要的限制如果我们只有方法1就不能支持在同一文件上构建多个索引在上面的例子中我们不能在 name 上支持二级索引。相反我们必须复制文件并在该文件上构建一个新的方法 1 索引。
2方法2按引用存储
在方法 2 中叶子页面保存指向相应记录的指针。 符号说明在上面的图表中叶节点包含KeyRecordID对其中 RecordID 是 [PageNumRecordNum]。
按引用进行索引允许我们在同一文件上拥有多个索引因为实际数据可以以任何顺序存储在磁盘上。
3方法3按引用列表存储
在方法 3 中叶节点保存指向相应记录的指针列表。与方法 2 相比当同一叶节点条目存在多个记录时这种方式更紧凑。现在每个叶节点包含KeyRecordID列表对。 6、聚类Clustering
现在我们已经讨论了记录如何存储在叶节点中我们还将讨论数据页上的数据如何组织。 集群/非集群是指数据页的结构方式。 由于叶页是方法1 的实际数据页并且键在索引叶页上排序因此方法1 索引默认情况下是聚集的。 因此去聚类仅适用于方法 2 或 3。
1非聚类Unclustered
在非聚类索引中数据页面是完全混乱的。因此很可能你需要为每个你想要的记录读取一个单独的页面。例如考虑这个图示 在上面的图中如果我们想要读取键为12和24的记录那么我们必须分别读取它们指向的每个数据页面以检索与这些键关联的所有记录。
2Clustered
在聚类索引中数据页面按照构建 B 树时使用的相同索引进行排序。这并不意味着数据页面是精确排序的只是键大致按照数据的顺序排列。因此I/O成本的差异主要来自缓存其中具有接近键的两个记录可能在同一页因此可以从缓存的页面中读取第二个记录。因此通常只需要读取一页即可获取具有公共/相似键的所有记录。例如考虑这个图示 在上面的图中我们可以通过读取 2 页来读取键为 7 和 12 的记录。如果我们按照叶节点值的顺序进行顺序读取数据页面基本相同。因此总的来说
非聚类 每条记录 ~ 1 次 I/O。聚类 每页记录 ~ 1 次 I/O。聚类 vs 非聚类索引尽管聚类索引在范围搜索方面可能更有效并在顺序磁盘访问和预取等方面提供潜在的局部性优势但它们通常比非聚类索引维护成本更高。例如随着越来越多的插入操作数据文件可能变得不太聚类因此需要定期对文件进行排序。
7、计算 I/O 次数
以下是一般的步骤。这是值得记录的 1. 读取适当的从根到叶子的路径。 2. 读取适当的数据页面。如果我们需要读取多个页面我们将为每个页面分配一次读取 I/O。此外我们需要考虑 Alt. 2 或 3 的聚类情况见下文。 3. 如果要修改数据页面则写入数据页面。同样如果我们要执行跨多个数据页面的写入我们需要为每个页面分配写入 I/O。 4. 更新索引页面。 让我们看一个例子。请参考以下的 Alternative 2 非聚类 B 树 我们想要从数据库中删除唯一的 11 岁。这将需要多少次I/O 1、每个 2 个相关的索引页面索引页面是内部节点或叶节点需要 1 次I/O。 2、读取 11 岁记录所在的数据页面需要 1 次 I/O。一旦它在内存中我们可以从页面中删除记录。 3、将修改后的数据页面写回磁盘需要 1 次 I/O。 4、现在我们的数据库中没有 11 岁了我们应该从 B 树的叶页面中删除键 11这是在步骤 1 中已经读取的。我们这样做然后将修改后的叶页面写回磁盘需要 1 次 I/O。 因此删除记录的总成本是 5 次 I/O。 8、批量加载
我们之前讨论的插入过程适用于对现有 B 树进行添加操作。然而如果我们要从头开始构建一个 B 树我们可以做得更好。这是因为如果我们使用插入过程每次插入新内容时都必须遍历整棵树对随机数据页面的常规插入也会导致缓存效率低和叶节点的利用率低因为它们通常是半空的。相反我们将使用批量加载 1、对将建立索引的键进行排序。 2、填充叶节点直到达到某个填充因子 f。注意填充因子仅适用于叶节点。对于内部节点我们仍然遵循相同的规则去插入直到它们被填满。 3、从父节点到叶节点添加指针。如果父节点溢出我们将执行与插入类似的过程。我们将父节点分成两个节点 - 在 L_1 中保留 d 个条目这意味着 d1 个条目将进入 L_2。 - 由于父节点溢出我们将 L_2 的第一个条目移动到父节点。 - 调整指针。 让我们看一个例子。假设我们的填充因子是 3/4我们想要将 1 到 20 插入到一个顺序 d2 的树中。我们将从填充叶节点开始直到达到填充因子 我们已经将一个叶节点填充到填充因子的 3/4并从父节点添加了一个指向叶节点的指针。让我们继续填充 在上面的图中我们看到父节点已经溢出。我们将父节点分成两个节点并创建一个新的父节点 从上面的例子中可以看出通过批量加载构建的索引始终以聚类方式开始因为底层数据是根据键排序的。为了保持聚类我们可以根据未来的插入模式选择填充因子。 以上DBS note2DIsks and Files
祝好。
