May 2020
Beginner to intermediate
319 pages
7h 3m
Chinese
Content preview from 数据库系统内幕
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
28
第
2
章
B 树基础知识
在上一章中，我们将存储结构分为两类：
可变存储结构
和
不可变存储结构
，并确定不可
变性为影响数据库设计和实现的核心概念之一。大多数可变存储结构使用
原地更新
的机
制。在插入、删除或更新操作期间，数据记录直接在目标文件中原本的位置被更新。
存储引擎通常允许同一数据记录在数据库中存在多个版本，例如：当使用多版本并发控
制（multi-version concurrency control，参见 5.3.6 节）或分槽页结构（参见 3.5 节） 时 。
为了简单起见，现在我们假设每个键只与一条数据记录相关联，且该数据记录具有唯一
的位置。
最流行的存储结构之一是 B 树。许多开源数据库系统都基于 B 树，多年来，这些数据库
已经被证明可以覆盖大多数的用例。
B 树并不是最近才发明的：它是由 Rudolph Bayer 和 Edward M. McCreight 于 1971 年便
引入的概念，此后其越来越流行。到了 1979 年，B 树已经有了相当多的变体，Douglas
Comer 收集并系统化地整理了其中一些变体 [COMER79]。
在深入研究 B 树之前，让我们先讨论一下为什么应该考虑替代传统搜索树（例如，二分
搜索树、2-3 树和 AV L 树 [KNUTH98]）。为此，我们先回顾一下什么是二分搜索树。
2.1
二分搜索树
二分搜索树
（BST）是一种有序的内存数据结构，可以用来高效地进行键值查找。二分
搜索树由多个节点组成，每个树节点由一个键、一个与该键关联的值以及两个子节点指
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.