B-tree(PostgreSQL 14 Internals翻译版)

概览

B树(作为B树访问方法实现)是一种数据结构,它使您能够通过从树的根向下查找树的叶节点中所需的元素。为了明确地标识搜索路径,必须对所有树元素进行排序。B树是为有序数据类型设计的,这些数据类型的值可以进行比较和排序。

下面的机场代码索引构建示意图将内部节点显示为水平矩形;叶节点垂直排列。

在这里插入图片描述
每个树节点包含几个元素,这些元素由一个索引键和一个指针组成。内部节点元素是下一层的引用节点;叶节点元素引用堆元组(图中没有显示这些引用)。

B树具有以下重要属性:

  • 它们是平衡的,这意味着树的所有叶节点都位于相同的深度。因此,它们保证所有值的搜索时间相等。
  • 它们有大量的分支,也就是说,每个节点包含许多元素,通常有数百个元素(为了清晰起见,该图仅显示了三个元素节点)。因此,B树深度总是很小,即使对于非常大的表也是如此。
  • 索引中的数据在每个节点内以及在同一级别的所有节点上按升序或降序排序。对等节点被绑定到一个双向列表中,因此可以通过简单地以一种或另一种方式扫描列表来获得有序的数据集,而不必每次都从根开始。

搜索与插入

等值搜索

让我们看一下如何根据条件“索引-列=表达式”在树中搜索值。我们将尽力找到KJA机场。

搜索从根节点开始,访问方法必须确定要下降到哪个子节点。它选择K i键,满足K i≤表达式< K i+1。

根节点包含键AER和OVB。条件AER < KJA<OVB成立,因此我们需要下降到具有AER键的元素所引用的子节点。

在这里插入图片描述

这个过程递归地重复,直到我们到达包含所需元组ID的叶节点。在这种特殊情况下,子节点满足条件DME≤KJA < KZN,因此我们必须下降到具有DME键的元素所引用的叶节点。

您可以注意到,树的内部节点中最左边的键是冗余的:要选择根的子节点,只要满足条件KJA < OVB就足够了。B树不存储这样的键,所以在下面的插图中,我将保留相应的元素为空。

叶节点中需要的元素可以通过二分查找快速找到。

然而,搜索过程并不像看起来那么简单。必须考虑到,索引中数据的排序顺序可以是升序(如上所示),也可以是降序。即使是唯一的索引也可以有几个匹配的值,并且必须返回所有这些值。此外,可能有太多的副本,以至于它们不适合单个节点,因此相邻的叶节点也必须处理。

最重要的是,当搜索正在进行时,其他进程可能会修改数据,页面可能被分成两个,树结构可能会发生变化。所有的算法都被设计为尽可能减少这些并发操作之间的争用,并避免过多的锁,但是我们在这里不打算讨论这些技术细节。

不等值搜索

如果搜索是通过条件“索引-列 ⩽expression”(或“索引-列⩾expression”)执行的,我们必须首先搜索满足相等条件的值的索引,然后在所需的方向遍历其叶节点,直到到达树的末端。

该图说明了搜索小于或等于DME的机场代码。

在这里插入图片描述
对于小于和大于操作符,过程相同,只是必须排除第一个找到的值。

范围搜索

当按照“表达式1≤索引列≤表达式2”的范围进行搜索时,我们必须先找到表达式1,然后沿着正确的方向遍历叶节点,直到找到表达式2。该图说明了在LED和ROV之间的范围内搜索机场代码的过程。

在这里插入图片描述

插入

新元素的插入位置由键的顺序明确定义。例如,如果将RTW机场代码插入到表中,则新元素将出现在ROV和SGC之间的最后一个叶节点中。

但是如果叶节点没有足够的空间容纳新元素怎么办?例如(假设一个节点最多可以容纳三个元素),如果我们插入TJM机场代码,最后一个叶节点将被过度填充。在这种情况下,节点被分成两个,旧节点的一些元素被移动到新节点中,指向新子节点的指针被添加到父节点中。显然,父节点也可能会被填满。然后它也被分成两个节点,以此类推。如果要拆分根,则在生成的节点之上再创建一个节点,以成为树的新根。在这种情况下,树的深度增加了一级。

在本例中,TJM机场的插入导致两个节点分裂;生成的新节点在下面的图中突出显示。为了确保可以拆分任何节点,双向列表绑定了所有级别的节点,而不仅仅是最低级别的节点。

在这里插入图片描述

所描述的插入和分割过程保证树保持平衡,并且由于节点可以容纳的元素数量通常相当大,因此树的深度很少增加。

问题是,一旦分裂,节点就永远无法合并在一起,即使它们在垃圾回收后包含的元素非常少。这个限制并不适用于B树数据结构本身,而是适用于它的PostgreSQL实现。因此,如果在尝试插入时发现节点已满,则访问方法首先尝试删除冗余数据,以便清除一些空间并避免额外的分割

页面布局

B树的每个节点占用一个页面。页的大小定义了节点的容量。

由于页面分割,树的根可以由不同时间的不同页面表示。但是搜索算法必须总是从根开始扫描。它在**零索引页(称为元页)**中查找当前根页的ID。元页面还包含一些其他元数据。

在这里插入图片描述

索引页中的数据布局与我们目前看到的略有不同。除了每个级别最右边的页面外,所有页面都包含一个额外的 “高键”,该键保证不小于该页中的任何键 。在上面的图表中,高音键被突出显示。

让我们使用pageinspect扩展来查看基于六位数预订引用的真实索引的页面。元页面列出根页面ID和树的深度(级别编号从叶节点开始,从零开始):

在这里插入图片描述
存储在索引项中的键被显示为字节序列,这不是很方便:

在这里插入图片描述
为了破译这些值,我们必须编写一个专门的函数。它不会支持所有平台,也可能不适用于某些特定场景,但它可以用于本章的示例:

在这里插入图片描述

现在我们可以看一下根页面的内容:

在这里插入图片描述

正如我所说的,第一个条目不包含键。ctid列提供到子页面的链接。

假设我们正在寻找预订E2D725。在这种情况下,我们必须选择条目19(因为E2CB14≥E2D725 < EF6FEA)并向下到第5135页。

在这里插入图片描述

本页中的第一个条目包含高键,这可能看起来有点出乎意料。从逻辑上讲,它应该放在页面的末尾,但从实现的角度来看,将它放在页面的开头更方便,以避免每次页面内容更改时都移动它。

在这里,我们选择条目3(因为E2D71D ⩽ E2D725 < E2E2F4),并向下到第11919页。

在这里插入图片描述
它是索引的叶子页。第一个入口是高键;所有其他条目都指向堆元组。

这是我们的预订单:

在这里插入图片描述
当我们按代码搜索预订时,低级别的情况大致就是这样:
在这里插入图片描述

重复数据删除

非唯一索引可以包含许多指向不同堆元组的重复键。由于非唯一键出现不止一次,因此占用大量空间,因此重复项被折叠成单个索引项,其中包含键和相应的元组ID列表。在某些情况下,这个过程(称为重复数据删除)可以显著减小索引大小。

但是,由于MVCC,唯一索引也可以包含重复项:索引保留对表行所有版本的引用。HOT更新机制可以帮助您避免由于引用过时的、通常寿命较短的行版本而导致的索引膨胀,但有时它可能不适用。在这种情况下,重复数据删除可以为清理冗余堆元组和避免额外的页面分割赢得一些时间。

为了避免在没有直接好处的情况下在重复数据删除上浪费资源,只有在叶子页没有足够的空间容纳另一个元组时才执行折叠。然后,页面修剪和重复数据删除可以释放一些空间,并防止不希望的页面分割。但是,如果副本很少,则可以通过关闭deduplicate_items storage参数来禁用重复数据删除特性。

部分索引不支持重复数据删除功能。主要的限制是键的相等性必须通过对其内部表示的简单二进制比较来检查。到目前为止,并不是所有的数据类型都可以用这种方式进行比较。例如,浮点数(浮点数和双精度数)对零有两种不同的表示。任意精度的数字(数字)可以用不同的尺度表示同一个数字,而jsonb类型可以使用这样的数字。如果使用非确定性排序,则不可能对文本类型进行重复数据删除,非确定性排序允许用不同的字节序列表示相同的符号(标准排序是确定性的)。

此外,复合类型、范围和数组以及用INCLUDE子句声明的索引目前不支持重复数据删除。

要检查特定索引是否可以使用重复数据删除,您可以查看其元页面中的allequalimage字段:

在这里插入图片描述

此时支持重复数据删除功能。事实上,我们可以看到,其中一个叶页包含具有单个元组ID (htid)和具有ID列表(tids)的索引条目:

在这里插入图片描述

内部索引项的紧凑存储

重复数据删除可以在索引的叶页中容纳更多条目。但是,即使叶页构成了索引的大部分,在内部页中执行数据压缩以防止额外的分割也同样重要,因为搜索效率直接依赖于树的深度。

内部索引项包含索引键,但它们的值仅用于在搜索期间确定要下降到的子树。在多列索引中,通常使用第一个键属性(或几个第一个键属性)就足够了。可以截断其他属性以节省页面中的空间。

这样的后缀截断发生在叶页被分割并且内页必须容纳一个新指针的时候。

例如,下面是在包含订票参考和乘客姓名的列上建立的票务表索引的根页的几个条目:

在这里插入图片描述

我们可以看到一些索引条目没有第二个属性。

当然,叶页必须保留所有键属性和INCLUDE列值(如果有的话)。否则,将无法执行仅索引扫描。唯一的例外是高键;它们可以部分保存。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/170588.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OpenCV视频车流量识别详解与实践

视频车流量识别基本思想是使用背景消去算法将运动物体从图片中提取出来&#xff0c;消除噪声识别运动物体轮廓&#xff0c;最后&#xff0c;在固定区域统计筛选出来符合条件的轮廓。 基于统计背景模型的视频运动目标检测技术&#xff1a; 背景获取&#xff1a;需要在场景存在…

基于PHP的线上购物商城,MySQL数据库,PHPstudy,原生PHP,前台用户+后台管理,完美运行,有一万五千字论文。

目录 演示视频 基本介绍 论文截图 功能结构 系统截图 演示视频 基本介绍 基于PHP的线上购物商城&#xff0c;MySQL数据库&#xff0c;PHPstudy&#xff0c;原生PHP&#xff0c;前台用户后台管理&#xff0c;完美运行&#xff0c;有一万五千字论文。 现如今,购物网站是商业…

【七】SpringBoot为什么可以打成 jar包启动

SpringBoot为什么可以打成 jar包启动 简介&#xff1a;庆幸的是夜跑的习惯一直都在坚持&#xff0c;正如现在坚持写博客一样。最开始刚接触springboot的时候就觉得很神奇&#xff0c;当时也去研究了一番&#xff0c;今晚夜跑又想起来了这茬事&#xff0c;于是想着应该可以记录一…

Python单元测试

import unittest #必须要导入单元测试的包class Student(object):def __init__(self, name, score):self.name nameself.score scoredef get_grade(self):if self.score > 100:#返回错误不能用return&#xff0c;应该用raise raise ValueError("成绩不能大于100"…

MySQL进阶(日志)——MySQL的日志 bin log (归档日志) 事务日志redo log(重做日志) undo log(回滚日志)

前言 MySQL最为最流行的开源数据库&#xff0c;其重要性不言而喻&#xff0c;也是大多数程序员接触的第一款数据库&#xff0c;深入认识和理解MySQL也比较重要。 本篇博客阐述MySQL的日志&#xff0c;介绍重要的bin log (归档日志) 、 事务日志redo log(重做日志) 、 undo lo…

【iOS逆向与安全】某音App直播间自动发666 和 懒人自动看视频

1.目标 由于看直播的时候主播叫我发 666&#xff0c;支持他&#xff0c;我肯定支持他呀&#xff0c;就一直发&#xff0c;可是后来发现太浪费时间了&#xff0c;能不能做一个直播间自动发 666 呢&#xff1f;于是就花了几分钟做了一个。 2.操作环境 越狱iPhone一台 frida m…

Mybatis应用场景之动态传参、两字段查询、用户存在性的判断

目录 一、动态传参 1、场景描述 2、实现过程 3、代码测试 二、两字段查询 1、场景描述 2、实现过程 3、代码测试 4、注意点 三、用户存在性的判断 1、场景描述 2、实现过程 3、代码测试 一、动态传参 1、场景描述 在进行数据库查询的时候&#xff0c;需要动态传入…

Linux友人帐之日志与备份

一、日志 1.1概述 日志文件是重要的系统信息文件&#xff0c;其中记录了许多重要的系统事件&#xff0c;包括用户的登录信息、系统的启动信息、系统的安全信息、邮件相关信息、各种服务相关信息等。日志对于安全来说也很重要&#xff0c;它记录了系统每天发生的各种事情&#…

openGauss学习笔记-108 openGauss 数据库管理-管理用户及权限-用户

文章目录 openGauss学习笔记-108 openGauss 数据库管理-管理用户及权限-用户108.1 创建、修改和删除用户108.2 私有用户108.3 永久用户108.4 用户认证优先规则 openGauss学习笔记-108 openGauss 数据库管理-管理用户及权限-用户 使用CREATE USER和ALTER USER可以创建和管理数据…

期中考核复现

web 1z_php ?0o0[]1A&OoO[]2023a include "flag.php"&#xff1a;尝试包含名为 "flag.php" 的文件。这意味着它会尝试引入一个名为 "flag.php" 的脚本文件&#xff0c;其中可能包含一些敏感信息或标志。 error_reporting(0)&#xff1a;…

MYSQL(事务+锁+MVCC+SQL执行流程)理解

一)事务的特性: 一致性:主要是在数据层面来说&#xff0c;不能说执行扣减库存的操作的时候用户订单数据却没有生成 原子性:主要是在操作层面来说&#xff0c;要么操作完成&#xff0c;要么操作全部回滚&#xff1b; 隔离性:是自己的事务操作自己的数据&#xff0c;不会受到到其…

【TES641】基于VU13P FPGA的4路FMC接口基带信号处理平台

板卡概述 TES641是一款基于Virtex UltraScale系列FPGA的高性能4路FMC接口基带信号处理平台&#xff0c;该平台采用1片Xilinx的Virtex UltraScale系列FPGA XCVU13P作为信号实时处理单元&#xff0c;该板卡具有4个FMC子卡接口&#xff08;其中有2个为FMC接口&#xff09;&#x…

机器学习中常见的特征工程处理

一、特征工程 特征工程&#xff08;Feature Engineering&#xff09;对特征进行进一步分析&#xff0c;并对数据进行处理。 常见的特征工程包括&#xff1a;异常值处理、缺失值处理、数据分桶、特征处理、特征构造、特征筛选及降维等。 1、异常值处理 具体实现 from scipy.s…

软件测试面试1000问(含文档)

前前后后面试了有20多家的公司吧&#xff0c;最近抽空把当时的录音整理了下&#xff0c;然后给大家分享下 开头都是差不多&#xff0c;就让做一个自我介绍&#xff0c;这个不用再给大家普及了吧 同时&#xff0c;我也准备了一份软件测试视频教程&#xff08;含接口、自动化、…

kvm webvirtcloud 如何添加直通物理机的 USB 启动U盘

第一步&#xff1a;查看USB设备ID 在物理机上输入 lsusb 命令 rootubuntu:/media/usb1# lsusb Bus 002 Device 002: ID 0781:5581 SanDisk Corp. Ultra Bus 002 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub Bus 001 Device 004: ID 0424:2514 Microchip Technolo…

进阶课3——神经网络

1.定义与分类 神经网络是一种模仿动物神经网络行为特征&#xff0c;进行分布式并行信息处理的算法数学模型。它由大量的节点&#xff08;或神经元&#xff09;相互关联而成&#xff0c;每个节点代表一种特定的输出函数&#xff08;或称为运算&#xff09;&#xff0c;称为激励…

音乐制作软件 Studio One 6 mac中文版软件特点

Studio One mac是一款专业的音乐制作软件&#xff0c;该软件提供了全面的音频编辑和混音功能&#xff0c;包括录制、编曲、合成、采样等多种工具&#xff0c;可用于制作各种类型的音乐&#xff0c;如流行音乐、电子音乐、摇滚乐等。 Studio One mac软件特点 1. 直观易用的界面&…

On Moving Object Segmentation from Monocular Video with Transformers 论文阅读

论文信息 标题&#xff1a;On Moving Object Segmentation from Monocular Video with Transformers 作者&#xff1a; 来源&#xff1a;ICCV 时间&#xff1a;2023 代码地址&#xff1a;暂无 Abstract 通过单个移动摄像机进行移动对象检测和分割是一项具有挑战性的任务&am…

计算机算法分析与设计(20)---回溯法(0-1背包问题)

文章目录 1. 题目描述2. 算法思路3. 例题分析4. 代码编写 1. 题目描述 对于给定的 n n n 个物品&#xff0c;第 i i i 个物品的重量为 W i W_i Wi​&#xff0c;价值为 V i V_i Vi​&#xff0c;对于一个最多能装重量 c c c 的背包&#xff0c;应该如何选择放入包中的物品…

论文-分布式-并发控制-Lamport逻辑时钟

目录 前言 逻辑时钟讲解 算法类比为面包店内取号 Lamport算法的时间戳原理 Lamport算法的5个原则 举例说明 算法实现 参考文献 前言 在并发系统中&#xff0c;同步与互斥是实现资源共享的关键Lamport面包店算法作为一种经典的解决并发问题的算法&#xff0c;它的实现原…