《数据库系统内 幕》B树的变体

news/2024/11/8 2:40:22/

B树的变体

  • 章六
    • 写时复制B树(COW)
    • 惰性B树
    • FD树
      • 分层级联的思想
    • Bw树
    • 缓存无关B树

专栏
《数据库系统内 幕》存储引擎
《数据库系统内 幕》事务恢复与处理
《数据库系统内 幕》日志结构存储
《数据库系统内 幕》B树的变体
《数据库系统内 幕》分布式系统

章六

B树的变体共同点:树结构、通过分裂合并实现平衡,以及查找和删除算法。
变体的区别:并发性、磁盘页表示、同级节点之间的链接和维护进程这些细节方面的不同。
写放大的问题:一个B树页后续更新可能需要每次更新时更新其磁盘驻留页副本。
空间放大问题:保留额外空间实现更新。

写时复制B树(COW)

这个变体是由于锁的等待时间而延申出来的结构。
实例:LMDB是一个使用写时复制的存储引擎。它不需要页缓存、预写日志、生成检查点或压实操作。
这是一个直接通过内存映射来满足读写操作,不用额外的缓存。
写时复制的过程:在更新时,找到目标子节点,将从根节点到目标子节点的路径中每个分支节点都被复制。更新所传播到的节点被修改,而其余节点将保持不变。在这里插入图片描述

实现思路:在对数据进行操作(增、删、改)之前,先把所有可能操作到的层级(所有祖先节点)数据块都拷贝一份出来(C’,B’,A’),后面的修改就在这份拷贝后的数据块上做修改,修改完之后再把这些数据块写入到磁盘文件新的位置上,这时候磁盘中就有两份数据,一份是修改之前的,一份是修改之后的,从修改之前的根节点开始遍历,可以读到所有修改之前的旧版数据,从修改之后的新根节点开始遍历,可以读到所有修改之后的新版数据。 从不同的根节点进去可以读取到不同版本的数据,这个CoW既保证了读写安全,也带有很优雅的数据备份功能(数据快照)。
同时当旧的根进行的读操作结束后,其页就会被回收,并且可以被重新使用。尽管保留很短的时间,还是一个占用更多的空间。(缺点)
MVCC全称Multi-Version Concurrency Control,即多版本并发控制,主要是为了提高数据库的并发性能

惰性B树

惰性B树降低了更新的成本,使用更轻量级的内存结构来缓冲并延迟传播更新。
实例:MongoDB中的存储引擎WiredTiger使用了惰性B树。
更新被保存到更新缓冲区中,在读取中访问更新缓存区,与原始磁盘页中内容合并,返回新数据。当刷写到磁盘上时,更新缓冲区内容与页内容协调然后保存在磁盘上。
优点:页更新和结构修改操作(分裂、合并)由后台线程执行,读写进程不必等待。
从单个节点缓冲更新延申到子树中,可以为每个子树附加用于批量操作得更新缓冲区。此时更新缓冲区将跟踪子树顶部节点及后代节点所执行得所有操作,称为惰性自适应树(LA树)在这里插入图片描述

在插入数据记录时,先加入根节点更新缓存区,在填满后我们将这些更改复制然后传播到较低层缓冲区,依次递归继续,直至叶节点。直到更新到达叶节点时,将在叶子层进行批量的插入、更新和删除操作,同时将所有更改应用于树的内容及结构。
优点:因为在更新子节点的过程中会产生分裂与合并操作可以传播到高层,所以这是一个减少磁盘访问的次数的方法,更加高效。

FD树

前面是通过创建辅助缓冲区来缓冲对单个节点或节点组的更新。还有另一种方法是通过仅追加存储和合并过程将不同节点更新归并在一起,将这种追加操作用于索引的例子叫做闪存盘树(Flash Disk Tree)。
FD树最重要的是分段级联思想,来维护层之间的指针。因为仅追加存储以及合并,将不同节点更新归并到一起,这意味这更新无需定位目标节点,只是单纯的追加操作。
在这里插入图片描述

FD树由一个小的,可变的头部树和多个不可变的有序段构成。随机IO产生时,会把更新缓冲在头部的小型B树中,一旦头部树被填满,就会把内容转移到不可变的有序段中,如果有序段超过阈值,就会和下一层合并。
FD树不在原地更新页,并且可能在几个层上存在相同键的数据记录,所以FD树使用墓碑来进行删除,类似一个标记,表示相应数据被删除,当墓碑被传到最底层的时候,就可以被丢弃了。因为此时可以保证没有需要它遮蔽的数据了。

分层级联的思想

比较简单,这个思想为了降低定位每个节点的成本,因为它可以帮助你在最接近的匹配项来进行搜索。
可以通过三个有序数组的例子了解这个思想。

Z = [12,24,32,34,39]
J = [22,25,28,30,35]
L = [11,16,24,26,30]

为了简化搜索,将下层数组中每隔几个元素(例子选择隔一个)就将一个元素拉到上层数组中来弥补元素间的间隔。

Z = [12,24,25,30,32,34,39]
J = [16,22,25,26,28,30,35]
L = [11,16,24,26,30]

把这些被挑出来的作为指针,由高层指向低层,则建立了级联结构。

Bw树

Bw树是通过仅追加存储来对不同节点进行批量更新解决这写放大与空间放大还有并发的问题。
每个节点由一个链表构成,链表末尾是基节点,其余是增量节点,增量节点表示更新插入,删除。并使用到了内存数据结构,该结构允许单个CAS操作在节点间建立指针,这种方法称Bw树。
CAS(V,E,N)操作是比较并交换,包含三个参数,内存地址V,E是预期值,N是新值。如果V上存放的值等于期望的值A,则将地址上的值赋为新值E,如果不等则自旋。

缓存无关B树

一个缓存无关B树由一个静态B树和一个打包的数组结构组成。静态B树使用van Emde Boas布局构建。在中间层的边上将树分裂,然后用类似方法分裂每个子树,最后得到大小为根号N的子树。这种布局的关键思想是,任何递归树都存储在一个连续内存块中。逻辑上,可以看到节点紧密形成树结构,底层存储可以看到树节点的内存和磁盘布局。

在这里插入图片描述
读不进去了,放一张杨舒宇的照片,哇,好好看,努力努力!


http://www.ppmy.cn/news/543754.html

相关文章

视觉3d中五折幕的震撼这就是沉浸式屏幕

近年来,沉浸式影厅已经成为了各大展馆及空间主流的展示形式,成熟的硬件与技术、随心定制的数字内容让它越来越多元化,多种折幕或LED屏的新颖组合不仅能带来震撼的感官冲击,还能营造立体有趣的互动体验。多折幕影厅就是沉浸式投影系…

《数据库系统内 幕》日志结构存储

日志结构存储 LSM树LSM思想LSM操作插入读删除 专栏 《数据库系统内 幕》存储引擎 《数据库系统内 幕》事务恢复与处理 《数据库系统内 幕》日志结构存储 《数据库系统内 幕》B树的变体 《数据库系统内 幕》分布式系统 LSM树 LSM树由两个或以上的存储结构组成。一个存储结构常驻…

【数据库专题】DML终极奥义——《狗叫江湖》“第五幕”

👏作者简介:东星耀杨,C站煮播之星,【无规则教学】创始人,曾奉太上老君之名下凡,为了给迷途中的兄弟萌指点迷津,帮助兄弟萌早日踏入如我这般境界!世人见我,皆称之“王霸之…

如何在premiere 中 裁切异形幕4K视频?

如何在premiere 中 裁切4K视频? 现实困境:L幕,墙幕和地幕是两个电脑投影投射的,所以需要分开输出的,成片是:3760x2690的分辨率;那么问题来了,H264支持4K格式,但是&#…

vue3第五幕之【工程结构】分析篇(vue2 vm VS vue3 app)

vue3 工程结构分析 vm vs app 前言主要内容1 工程结构分析1.1 图示1.2 叙述 2 vue3工程结构2.1 app与vm2.2 App.vue2.3 语法检查 summary下期预告vue3第六幕之组合式API篇(初识setup()) 前言 这篇文章的相关知识在vue3第一幕基础与起步中有过提及,本文相…

入眠时分闭上眼睛的时候眼睑闭上的那一瞬间今天的一切落下帷幕 下了绵绵的细雨洋洋洒洒,飘忽不定微风吹过凉意融融天空似乎蒙上了细细的幕幕如淡墨,染尘轻盈 路人匆匆而过亦步亦趋之间,我自默然人心入幕,幕似围城冰释不在&#xf…

ue4 unreal NDisplay插件 简易使用 三折幕 详细...

仅支持4.27版本 NDisplay文档 https://docs.unrealengine.com/4.27/en-US/WorkingWithMedia/IntegratingMedia/nDisplay/Overview/ Switchboard文档 https://docs.unrealengine.com/4.27/en-US/WorkingWithMedia/CommunicatingWithMediaComponents/Switchboard/ 1.打开任意项…

LGSS-一种多模态电影幕分割方法

1.简介 该方法发布于IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2020,由 港中文商汤联合实验室与香港中文大学深圳合作发作 GitHub地址:https://github.com/AnyiRao/SceneSeg 网站地址:https://anyirao.com/projec…