当前位置：首页 > news >正文

数据库基础-B+树

news 来源：原创 2025/8/7 10:46:11

在这里插入图片描述

查询类型

全表扫描，不提供索引，扫描所有集合中的数据。
根据指定key值查询指定点
范围查询，在指定区间内查询

有很多方法能够进行快速扫面数据，但是再快复杂度也是O(N)，我们的目标是想办法将查询复杂度降低到O(logN)。

A range query consists of 2 phases:

Seek: find the starting key.
Iterate: find the previous/next key in sorted order.

哈希表

在讨论如何构建哈希表（hashtable），尤其是内存中的哈希表时，确实存在一些挑战。尽管如此，相较于之后会编写的B树，编写哈希表还是相对简单的。以下是一些需要考虑的问题和解决方案：

如何扩展哈希表？ 当负载因子过高时，意味着当前哈希表的容量不足以有效地处理更多的键值对，这时就需要将键迁移到一个更大的哈希表中。如果一次性移动所有数据，其时间复杂度为Ο(Ν)，这在实际应用中是非常不理想的。因此，重新散列(rehashing)必须渐进式地进行，即使是像Redis这样的内存应用程序也应如此。一种常见的做法是在每次插入新键值对时，随机选择一定比例的旧键值对进行重散列，直到所有键都被迁移至新的哈希表。
其他提及的事项：
- 就地更新（In-place updates）: 这指的是直接在现有存储位置上更新键值对，而不是删除再插入。这对于保持哈希表的性能非常重要。
- 空间复用（Space reuse）: 有效管理哈希表的空间使用情况，包括回收被删除键值对占用的空间，以减少内存碎片并提高内存使用效率。

排序数组

讨论完哈希表后，让我们转向最简单的排序数据结构：排序数组（sorted array）。对于如字符串这样的可变长度数据（键值对），可以使用指针（或偏移量）数组来进行二分查找，其时间复杂度为Ο(log Ν)。

然而，更新排序数组的成本是Ο(Ν)，无论是否就地更新。这意味着直接在排序数组中进行插入和删除操作并不是非常实用，尤其是在需要频繁更新的场景下。不过，这种结构可以通过一些方式扩展成更复杂的、支持高效更新的数据结构。

一种减少更新成本的方法是将数组分割成几个较小的、互不重叠的数组——即嵌套排序数组。这种扩展最终可以发展为B+树（多级n叉树），但同时也带来了维护这些小数组（即树节点）的额外挑战。

另一种形式的“可更新数组”是日志结构合并树（Log-Structured Merge Tree, LSM树）。在这种结构中，更新首先被缓冲在一个较小的数组（或其他排序数据结构）中，当这个数组变得过大时，再与主数组合并。通过将较小数组逐步合并到较大数组中的方式，摊销了更新成本。

LSM树的设计旨在优化写入密集型应用场景，它通过对数据进行批量处理来提高效率，尽管这可能会以增加读取操作的复杂性为代价。这种方法非常适合于需要处理大量写入操作的应用程序，例如数据库系统。通过这种方式，不仅解决了原始排序数组更新成本高的问题，还提供了一种有效管理大规模数据集的方法。

MVCC也是为了应对写密集型

B树

B树是一种平衡的n叉树，类似于平衡二叉树。每个节点可以存储多达𝑛个键（和分支），其中𝑛大于2。B树的设计主要是为了减少磁盘随机访问次数，从而提高查询效率。

减少随机访问次数

由于磁盘每秒只能执行有限数量的IO操作（IOPS），这是查找操作的主要限制因素。在进行查找时，树的每一层都对应一次磁盘读取。对于相同数量的键，n叉树比二叉树更短（log𝑛 𝑁对比log₂ 𝑁），因此使用n叉树可以减少每次查找所需的磁盘读取次数。

选择𝑛值时存在权衡：

较大的𝑛值意味着每次查找需要的磁盘读取次数较少，这能改善延迟和吞吐量。
但是，较大的𝑛值也意味着节点更大，更新速度较慢（这将在后面讨论）。

磁盘IO的基本单位是页面

虽然你可以从文件的任意偏移量读取任意数量的字节，但磁盘并不是这样工作的。磁盘IO的基本单位不是字节，而是扇区，在旧的HDD上，扇区是512字节的连续块。

然而，应用程序并不直接关心磁盘扇区，因为常规文件IO不直接与磁盘交互。操作系统会在页缓存中缓存/缓冲磁盘读写，页缓存由称为“页”的4KB内存块组成。

无论如何，存在一个最小的IO单位。数据库也可以定义自己的IO单位（也称为“页”），其大小可能超过操作系统的页大小。

最小IO单位意味着树节点应该以该单位的倍数分配；如果一个单位只使用了一半，则另一半就浪费了IO资源。这也是反对使用较小的𝑛值的另一个原因！

通过确保树节点的大小为IO基本单位的整数倍，可以最大化利用每一次IO操作，减少因未充分利用IO单位而造成的浪费。这对于优化数据库性能至关重要，尤其是在处理大量数据和高并发场景时。此外，考虑到节点大小对更新性能的影响，合理选择𝑛值可以在查询性能和更新成本之间取得平衡。

B+树的优势

在数据库的上下文中，提到的B树通常指的是其一种变体——B+树。B+树的特点是内部节点不存储实际值，只存储键和指向子节点的指针；所有的值仅存在于叶节点中。这种设计使得B+树的内部节点可以容纳更多的分支，从而导致树的高度更矮、结构更扁平。

缩短树的高度：由于内部节点无需存储数据值，它们可以使用更多的空间来存储键和指针，这允许每个节点包含更多的子节点，从而降低了树的高度。
内存中的B+树：即使作为内存中的数据结构，B+树依然有意义。例如，在RAM与CPU缓存之间，最小的IO单位是64字节（缓存行）。尽管在这种情况下性能提升不如磁盘上的那么显著，因为64字节能容纳的数据量有限，但优化仍然有效。

数据结构的空间开销

二叉树在实际应用中往往不太实用的一个原因是其大量的指针开销。对于每个键，至少需要一个来自父节点的指针。而在B+树中，多个键共享一个来自父节点的指针，这样就大大减少了指针的数量和因此带来的空间开销。

此外，B+树的叶节点中的键还可以以紧凑格式存储或进行压缩，以进一步减少空间占用。这种方式不仅节省了存储空间，也提高了缓存的命中率，进而提升了访问效率。通过这些优化措施，B+树能够在保证高效查询的同时，也能够有效地管理空间使用，使其成为许多数据库系统底层存储结构的首选。

日志结构存储（Log-structured Storage）

Update by merge: amortize cost

日志结构存储的核心思想是通过“合并”操作来摊销更新成本，其中最典型的例子是日志结构合并树（LSM-tree）。尽管名字中包含“日志”和“树”，但其核心机制实际上是合并。

基本原理：双文件系统

我们从两个文件开始：

小文件：用于存储最近的更新。
大文件：用于存储其余的数据。

更新首先写入小文件，但小文件不能无限增长。当小文件达到某个阈值时，它会被合并到大文件中。

writes => | 新更新 | => | 积累的数据 |file 1         file 2

合并操作会生成一个新的、更大的文件，用以替换旧的大文件，同时清空小文件。合并的时间复杂度为𝑂(𝑁)，但由于合并可以与读写操作并发执行，因此不会显著影响性能。

多级合并：减少写放大效应

缓冲更新比每次重写整个数据集更高效，但如果我们将这种机制扩展到多个层级，效果会更好：

              | 第1层 |||\/|------第2层------|||\/
|-----------------第3层-----------------|

在两级方案中，每当小文件达到阈值时，大文件都会被重写。这种额外的磁盘写入称为写放大效应（write amplification）。随着大文件的增长，写放大效应会变得更加严重。

通过引入更多层级，我们可以将第2层保持较小规模，将其合并到第3层，类似于如何保持第1层的小规模。直观上，每一层的大小呈指数增长（例如，第2层是第1层的两倍，第3层是第2层的两倍），并且将规模相似的层级进行合并可以最小化写放大效应。

写放大效应与层级数量的权衡

虽然增加层级数量可以有效减少写放大效应，但这也会对查询性能产生负面影响：

更多的层级意味着查询时可能需要访问更多的文件，从而增加了查询的复杂性。
更少的层级则可能导致更高的写放大效应。

因此，在设计LSM-tree时，需要在写放大效应和查询性能之间找到平衡点。

总结

日志结构存储（如LSM-tree）通过合并操作摊销了更新成本，并通过多级结构进一步优化了写放大效应。其关键特点包括：

高效的写入性能：更新被缓冲在小文件中，避免频繁重写整个数据集。
可控的写放大效应：通过多级合并，减少不必要的磁盘写入。
灵活性：可以根据具体应用场景调整层级数量，权衡写放大效应和查询性能。

LSM-tree 索引

在 LSM-tree 中，每一层都包含索引数据结构。由于除第 1 层外的所有层都不会被直接更新，因此一个简单的选择是使用排序数组作为索引。然而，二分查找在随机访问上的性能优势并不比二叉树显著，因此更合理的做法是在每一层中使用 B 树，这就是 LSM-tree 名字中的“树”部分。

无论如何，由于缺乏直接的更新操作，数据结构的设计变得更加简单。

合并的思想与哈希表的类比

为了更好地理解“合并”的思想，可以尝试将其应用于哈希表。这种设计被称为日志结构哈希表（log-structured hashtable）。尽管实现方式不同，但其核心思想仍然是通过缓冲和合并来优化写入性能。

LSM-tree 查询

在 LSM-tree 中，键可能存在于任何层级中，因此查询时需要将所有层级的结果结合起来：

范围查询：采用多路归并（n-way merge）。
点查询：可以通过布隆过滤器（Bloom filters）优化，减少需要搜索的层级数量。

由于旧层级不会被更新，因此可能存在旧版本的键，而删除的键会在新层级中标记为特殊标志（称为墓碑，tombstone）。因此，在查询时，新层级具有优先级。

合并过程会自然地回收旧键或已删除键占用的空间，这个过程也被称为压缩（compaction）。

实际应用中的 LSM-tree：SSTable、MemTable 和日志

这些术语描述了 LSM-tree 的实现细节。虽然从原理上构建 LSM-tree 不需要了解它们，但它们确实解决了一些实际问题。

SSTable（Sorted String Table）
每一层被分成多个互不重叠的文件，而不是一个大文件。这样做的好处包括：
- 合并操作可以逐步进行，避免一次性合并大文件所需的大量空闲空间。
- 合并过程可以分散到时间上，降低峰值资源需求。
日志（Log）
第 1 层可以直接更新，但由于其大小有限，使用日志是一个合理的选择。这是 LSM-tree 名字中的“日志”部分，展示了如何将日志与其他索引数据结构结合使用。
MemTable
即使日志很小，仍然需要一个适当的索引数据结构来加速查询。日志数据会被复制到内存中的索引结构，称为 MemTable。MemTable 可以是 B 树、跳表（skiplist）或其他结构。它是一个小而有界的内存数据结构，能够加速对最近更新的读取场景。

索引数据结构的总结

目前有两种主要的索引数据结构选择：

B+树
B+树适用于需要频繁更新的场景，但在磁盘上的更新效率较低，并且空间复用的问题需要额外处理。
LSM-tree
LSM-tree 解决了许多上一章提到的挑战，例如如何高效更新基于磁盘的数据结构以及如何复用空间。虽然这些问题对于 B+树依然存在

总结对比

特性	B+树	LSM-tree
更新效率	较低（每次更新需维护树结构）	高效（通过合并摊销成本）
查询效率	快速（单次查询即可找到目标）	较慢（需多层查询与合并）
空间复用	需要额外机制	自然支持（通过压缩回收空间）
适用场景	频繁读取与少量更新	写密集型工作负载

通过理解这两种数据结构的特点，可以根据具体应用场景选择最适合的解决方案。

数据库基础-B+树

查询类型全表扫描，不提供索引，扫描所有集合中的数据。根据指定key值查询指定点范围查询，在指定区间内查询有很多方法能够进行快速扫面数据，但是再快复杂度也是O(N)，我们的目标是想办法将查询复杂度降低到O(logN)。…...

编程日记 2025/8/7 10:46:11

智能语音备忘录：SpeechRecognition与gTTS的奇妙融合

引言：智能语音备忘录的时代已经到来在这个信息爆炸的时代，我们每天需要处理大量的事务和信息。传统的文字记录方式虽然可靠，但在效率上往往难以满足快节奏生活的需求。想象一下，如果你能在驾车、散步或是灵感突现的任何时刻&…...

编程日记 2025/8/7 10:41:43

C++项目 —— 基于多设计模式下的同步异步日志系统（3）（日志器类）

C项目 —— 基于多设计模式下的同步&异步日志系统（3）（日志器类） 整体思想设计日志消息的构造C语言式的不定参函数的作用函数的具体实现逻辑1. 日志等级检查2. 初始化可变参数列表3. 格式化日志消息4. 释放参数列表5. 序列化和…...

编程日记 2025/8/6 20:35:18

2025/4/19 数据库的流程控制函数

单行函数_流程函数要点: 流程处理函数可以根据不同的条件执行不同的处理流程可以在SQL语句中实现不同的条件选择,MySQL中的流程处理函数主要包括if() ifnull() 和 case() 函数多行函数_聚合函数和单行函数的区别: 单行函数是作用在每一行最终结果可能是多行结果多行…...

编程日记 2025/8/7 10:41:43

代码随想录打家劫舍+树形DP入门

动态规划part07 198.打家劫舍视频讲解：https://www.bilibili.com/video/BV1Te411N7SX https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html dp数组：进入房屋i能够偷得得最大金额dp[i]递推公式：根据不相邻原则…...

编程日记 2025/8/7 10:35:43

Http基础

目录定义一、请求部分（Request） 1. 请求行（Request Line） 常见请求方法： 2. 请求头（Request Headers） 3. 请求体（Request Body） 二、响应部分（Respo…...

编程日记 2025/8/7 10:42:23

【Unity】bug记录——部分物体突然不受animator控制

博主烘焙完灯光后突然发现有的物体的动画失效了，不会动，测试发现是因为勾了static（但是有些勾了static的物体就没事），修改static为Contribute GI Static（只针对光照静态）就行...

编程日记 2025/8/7 10:42:20

Zephyr、FreeRTOS、RT-Thread 邮箱（Mailbox）对比分析

一、核心特性对比特性ZephyrFreeRTOSRT-Thread消息类型支持指针或4字节数据（依赖架构）仅支持指针传递支持任意数据类型（需指定消息长度）容量固定容量（静态初始化配置）动态容量（基于队列长度&a…...

编程日记 2025/8/7 10:41:44

xilinx fpga中pll与mmcm的区别

Xilinx中的PLL（锁相环）和MMCM（混合模式时钟管理器）都是用于时钟管理的关键组件，但它们之间存在一些显著的区别。以下是对两者的详细比较： 1. 功能特性 PLL（锁相环）： 主…...

编程日记 2025/8/7 10:46:10

Python语法系列博客 · 第8期[特殊字符] Lambda函数与高阶函数：函数式编程初体验

上一期小练习解答（第7期回顾） ✅ 练习1：找出1~100中能被3或5整除的数 result [x for x in range(1, 101) if x % 3 0 or x % 5 0]✅ 练习2：生成字符串长度字典 words ["apple", "banana", "grape…...

编程日记 2025/8/7 10:44:30

黑马商城（五）微服务保护和分布式事务

一、雪崩问题二、雪崩-解决方案（服务保护方案） 请求限流： 线程隔离： 服务熔断： 服务保护组件： 三、Sentinel 引入依赖：  <dependency><groupId>com.aliba…...

编程日记 2025/8/7 8:29:39

Java 编译与反编译深度解析

Java 编译与反编译深度解析 1. 编译过程详解 (1) 完整编译流程 .java 文件 → 词法分析 → 语法分析 → 语义分析 → 字节码生成 → .class 文件│ │ │ │↓ ↓ ↓ ↓识别关键字生成抽象语法树类型…...

编程日记 2025/8/1 1:38:55

Java集合框架中的List、Map、Set详解

在Java开发中，集合框架是处理数据时不可或缺的工具之一。今天，我们来深入了解一下Java集合框架中的List、Map和Set，并探讨它们的常见方法操作。目录一、List集合 1.1 List集合介绍 1.2 List集合的常见方法添加元素获取元素修改元素…...

编程日记 2025/8/7 10:33:06

国产的 Java Solon v3.2.0 发布（央企信创的优选）

Solon 框架！ Solon 是新一代，Java 企业级应用开发框架。从零开始构建（No Java-EE），有灵活的接口规范与开放生态。采用商用友好的 Apache 2.0 开源协议，是“杭州无耳科技有限公司”开源的根级项目&#xff…...

编程日记 2025/8/7 10:45:52

机器学习决策树

一、何为决策树决策树（Decision Tree）是一种分类和回归方法，是基于各种情况发生的所需条件构成决策树，以实现期望最大化的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。它的运行机制非常通俗易…...

编程日记 2025/8/7 10:35:31

Java集合及面试题学习

知识来源沉默王二、小林coding、javaguide 1、ArrayList list.add("66") list.get(2) list.remove(1) list.set(1,"55") List<String> listnew ArrayList<>(); 底层是动态数组添加元素流程：判断是否扩容&#xf…...

编程日记 2025/8/6 15:09:13

【内置函数】84个Python内置函数全整理

Python 内置函数全集（完整分类参数详解示例） 文章目录 Python 内置函数全集（完整分类参数详解示例）一、数值与数学函数abs(x)divmod(a, b)pow(x, y, modNone)round(number[, ndigits])sum(iterable, /, start0)hash(obj) …...

编程日记 2025/8/7 10:38:21

【LeetCode 热题 100】双指针系列

📁283. 移动零对于该题目，需要注意的是两个地方，一是保持非零元素的相对顺序，以及O(1)的空间复杂度。采用双指针的思路，将数组划分成3个区间,。 [0 , left]：该区间内元素全是非零元素。 [left1 , right…...

编程日记 2025/8/7 10:44:30

实现批量图片文字识别(python+flask+EasyOCR)

话不多说,向上效果图 1)先说框架版本为什么要先说框架版本呢,因为我在各种版本中尝试了两天,总算确定了如下版本适合我,至于其他的版本,各位自己去尝试 python 3.9.7 EasyOCR 1.7.2 flask 3.0.3 2)执行操作效果图 2.1)多选文件 2.2)图片预览 2.3)提取选中文件 2.4)提取所有文…...

编程日记 2025/8/3 7:20:14

[Swift]pod install成功后运行项目报错问题error: Sandbox: bash(84760) deny(1)

操作： platform :ios, 14.0target ZKMKAPP do# Comment the next line if you dont want to use dynamic frameworksuse_frameworks!# Pods for ZKMKAPPpod Moyaend pod install成功后运行报错报错： error: Sandbox: bash(84760) deny(1) file-writ…...

编程日记 2025/8/6 13:36:41

文档内容提取以及合成

如何从10个左右的docx文档中抽取内容，生成新的文档，抽取内容包括源文档的文字内容、图片、表格、公式等，以及目标文档的样式排版、字体、格式，还有目标文档的语言风格、用词规范、文法习惯等等。这是一个相当复杂的需求&#xff0…...

编程日记 2025/8/4 9:33:52

[Windows] Wireshark 网络抓包工具 v4.4.6

[Windows] Wireshark 网络抓包工具链接：https://pan.xunlei.com/s/VOODTZ7Lm2gsNLoFNcOIqflzA1?pwdf3ea# 软件说明Wireshark（前称Ethereal）是一款免费开源的网络嗅探抓包东西，世界上最流行的网络协议剖析器！网络封…...

编程日记 2025/8/6 14:10:58

在Ubuntu中安装hadoop的详细过程

在Ubuntu中安装hadoop的详细过程请自行安装Ubuntu系统（可参考：在VMWare中安装Linux虚拟机Ubuntu） 一、创建hadoop用户如果在安装 Ubuntu 的时候不是用的 “hadoop” 用户，这时需要增加一个名为 hadoop 的用户。首先打开终端…...

编程日记 2025/8/1 17:12:03

NOIP2017提高组.列队

目录 *数据结构模板题目算法标签: 模拟, 线段树, 线段树动态开点, 树状数组, 平衡树思路*前置代码完整注释代码精简注释代码 *数据结构模板题目 530. 列队算法标签: 模拟, 线段树, 线段树动态开点, 树状数组, 平衡树思路首先考虑简单情况, 如果只有一行, 删除一个位置…...

编程日记 2025/8/7 10:40:17

PSN港服跳过生日找回密码（需要英语对话，需要注册的id）

登陆这个网站 https://www.playstation.com/en-hk/support/contact-us/?categoryAcc&subCategorypw 随便输入点名字 firstname 跟lastname 勾选，然后打开机器人聊天然后按照提示输入邮箱跟id，输入正确之后会分配真人客服真人客服会要求提供第一次…...

编程日记 2025/8/7 10:46:11

服务治理-服务注册

一个服务在真实项目部署的时候，如果压力较大，会做多实例部署。在IDEA里面做多实例部署的话，只需要配置多个启动项。...

编程日记 2025/8/1 9:29:22

Jinja2模板引擎SSTI漏洞

1. 引入再研究大模型相关应用的漏洞CVE-2025-25362时（参考1），看到作者给了比较详细的分析（参考2）。下面对这个漏洞做个介绍。 2. 漏洞类型这个漏洞属于CWE-1336，它主要关注在使用模板引擎进行脚本化处…...

编程日记 2025/8/7 10:44:07

STM32单片机教程：从零开始打造智能天气时钟

STM32单片机教程：从零开始打造智能天气时钟大家好！今天我想为大家详细介绍一下我们的STM32课程，以及如何从零基础逐步掌握单片机开发技能，最终实现一个完整的智能天气时钟项目。课程面向人群本课程主要面向那些已经通过野火…...