究竟是什么让OLTP数据库能够如此快速地查找数据？

点击标题下「蓝色微信名」可快速关注

技术社群的这篇文章《是什么让OLTP数据库能够如此快速地查找数据？》，是Vu Trinh写的这篇文章的译文，给我们讲解了关系型数据库B-Tree的数据结构，虽然数据库不同，但原理相通，可以学习借鉴。

原文链接，可以看下原版，

https://vutr.substack.com/p/what-makes-oltp-databases-so-quick

前言

作为一名数据工程师，我并没有花太多时间去使用像 PostgreSQL 这样的 OLTP 数据库。我知道，为了让数据库中的数据操作变快，必须有一些技术来提升数据库所支持典型工作负载的性能。对于 OLAP 系统来说，最终目标是尽可能多地剪枝数据。

对于 OLTP 系统来说，目标是尽可能快地找到一条记录。

但它们是怎么办到的呢？

图片

在本文中，我们将深入探讨在 PostgreSQL 和 MySQL 这类数据库中，用于优化查询性能的最流行技术：B-Tree。我们首先学习内存中树数据结构的基础知识，并利用这些知识逐步建立对 B-Tree 的理解。

一、树

在计算机科学中，树用来模拟一种层次结构。数据被安排在节点中，这些节点按层次链接。以下术语定义了任何树结构：

图片

图片

图片

二、二叉树

图片

图片

图片

图片

图片

三、平衡

图片

四、二叉树在磁盘上不能很好地工作

图片

图片

图片

五、B树

鉴于大多数关系型数据库将数据存储在磁盘上，它们需要对 BST 进行改进。于是 B-Tree 出现了。

图片

六、剖析

在经典的 B-Tree 实现中，数据可以存储在非叶子节点中。在变种 B+ Tree 中，只有叶子节点保存数据。

图片

图片

• 一个根节点：每个数据操作都必须从这里开始。

图片

• 叶子节点存储指向实际数据的指针。更详细地说，它们存储键值对；键是索引列的值，值是指向实际数据的指针。
• 内部节点将根和叶子连接在一起。

对于非叶子（根和内部）节点，它们存储：

图片

• 键，即索引列的值。非叶子节点将拥有一段连续的排序键（排序以启用二分搜索）。
• 指向其他节点的指针。
• 指针的数量等于键的数量 + 1。
• 指针将指向一个子树，该子树的键范围在 [ key_left, key_right )

图片

数据操作归结于找到所需的数据节点。读取和更新数据是类似的过程。更详细地说，过程如下：

图片

• 一个带有索引列过滤器的查询，可以是点查找或范围过滤（=、<、>、between），例如通过客户 ID 获取客户。（此查询在 OLTP 工作负载中非常普遍）
• 搜索操作从树的根节点开始。
• 数据库将搜索值与节点中存储的键进行比较，以确定跟随哪个子指针。
• 此过程重复进行，一次下降一层，直到到达包含所需数据的叶子节点。

七、节点已满

图片

• 如果它是非叶子节点，新节点的第一个键将被移动到父节点中。

图片

对于叶子节点的情况，通过将此键复制到父节点，该键现在充当导航指南。父节点说：“任何小于该键的去我的左孩子，任何大于或等于该键的去我的右孩子。”

对于内部节点的情况，将此键移动到父节点充当分割。它不再需要存在于子节点级别，因为它的唯一目的是分割那些现在位于两个独立节点中的键。由于此级别没有数据指针，移动该键不会导致丢失对任何数据的访问。

如果父节点也溢出了，它们也必须被分裂。这种分裂操作可能需要递归地一直进行到根节点。

八、节点未充分利用

与溢出相反的情况，称为下溢，即一个节点包含的键数少于最小键数限制（N/2）。这可能在用户删除数据时发生。解决此情况的过程与系统解决溢出的方式正好相反。

想法很简单：如果两个相邻节点（兄弟节点）拥有同一父节点，并且它们的总键数可以放入一个节点中，它们应该被合并：

• 如果它是叶子节点，它与相邻兄弟节点合并。一个节点的所有键指针对被移动到另一个节点中。结果是一个包含两者所有键的单一叶子节点。分隔这两个叶子节点的父内部节点中的键被删除。

图片

• 如果它是非叶子节点，它也与相邻兄弟节点合并。系统必须首先拉下其父节点中的分隔键。该键加入两个待合并节点的键中。下溢节点、其兄弟节点以及拉下的父键的所有键和所有子指针被合并成一个新的单一内部节点。

图片

与溢出情况一样，解决下溢的过程可能需要一直进行到根节点。

九、使其可靠

结语

>>>>

参考资料

• 【1】Martin Kleppmann，《设计数据密集型应用程序》（2017） https://www.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/
• 【2】Alex Petrov，《数据库内部：深入探究分布式数据系统的工作原理》（2019） https://www.amazon.com/Database-Internals-Deep-Distributed-Systems/dp/1492040347
• 【3】CS186，伯克利，B+Tree 注释，（2023） https://cs186berkeley.net/resources/static/notes/n04-B+Trees.pdf

如果您认为这篇文章有些帮助，还请不吝点下文章末尾的"点赞"和"在看"，或者直接转发朋友圈，

图片