Hxy's Ocean

梦为努力浇了水

爱在背后往前推

累到整夜不能睡

夜色哪里都是美

别等到一千年以后

所有人都遗忘了我

Slides
Notes

1. 其他索引用法

• 隐式索引（Implicit Indexes）：大多数DBMS会自动创建索引来实施完整性约束(例如，主键、唯一约束)。

• 部分索引（Partial Indexes）：在整个表的子集上创建索引，（where语句形成子集）。这可能会减少大小和维护开销。

• 覆盖索引（Covering Indexes）：处理查询所需的所有属性都在索引中可用，则DBMS不需要检索元组。DBMS只需根据索引中可用的数据即可完成整个查询。（即，索引的数据中就能满足本次查找，不需要再去检索元组了，无需回表操作）

• 索引包含列（Index Include Columns）：在索引中嵌入其他列以支持仅索引查询。

• 函数/表达式索引（Function/Expression Indexes）：将函数或表达式的输出存储为键，而不是原始值。DBMS的工作是识别哪些查询可以使用该索引。

2. Radix Tree 基数树

一个 radix tree 是 Trie数据结构的变体。它使用 key 的 digital 表示来逐个检查前缀，而不是比较整个 key 。它与trie的不同之处在于，key 中的每个元素都没有一个节点，在key不同之前，节点被合并以表示最大的前缀。

Radix tree 的高度取决于 key 的长度，而不是像B+树那样取决于 key 的数量。指向叶节点的路径表示叶的关键字。并非所有属性类型都可以分解为基数树的二进制可比数字。

对于长整型数据的映射，如何解决Hash冲突和Hash表大小的设计是一个很头疼的问题。

radix树就是针对这种稀疏的长整型数据查找，能快速且节省空间地完成映射。借助于Radix树，我们可以实现对于长整型数据类型的路由。利用radix树可以根据一个长整型（比如一个长ID）快速查找到其对应的对象指针。这比用hash映射来的简单，也更节省空间，使用hash映射hash函数难以设计，不恰当的hash函数可能增大冲突，或浪费空间。

Radix tree是一种多叉搜索树，树的叶子结点是实际的数据条目。每个结点有一个固定的、2^n指针指向子结点（每个指针称为槽slot，n为划分的基的大小）

Trie树一般用于字符串到对象的映射，Radix树一般用于长整数到对象的映射。

3. Inverted Indexes 倒排索引

倒排索引存储单词到目标属性中包含这些单词的记录的映射。在DBMS中，这些索引有时称为全文搜索索引。

大多数主要的DBMS本身都支持倒排索引，但也有专门的DBMS，其中这是唯一可用的表索引数据结构。

（君如理解：倒排索引，它可以进行关键字搜索，因为hash索引和B+树索引对这个的性能都不太好。关键字搜索，主要是怕key的容量非常大。因此可以通过将关键词单词映射到包含单词的一些记录中。）

查询类型：

• 短语搜索：查找按给定顺序包含单词列表的记录。

• 邻近搜索：查找两个单词在彼此的单词内出现的记录。

• 通配符搜索：查找包含匹配某种模式(例如，正则表达式，like)的单词的记录。
  设计决策：

• 存储什么：索引需要至少存储每个记录中包含的单词(由标点符号分隔)。它还可以包括其他信息，例如词频、位置和其他元数据。

• 何时更新每次修改表时更新倒排索引既昂贵又慢。因此，大多数DBMS将维护辅助数据结构以“暂存”更新，然后批量更新索引。

Slides
Notes

1. 索引 Indexes

我们将重点介绍数据库中的数据结构——表索引。

表索引是表中列的子集的副本，其组织方式使DBMS能够比执行顺序扫描更快地找到元组。DBMS确保表和索引的内容始终同步。

DBMS的工作是找出用于执行查询的最佳索引。在每个数据库要创建的索引数量上存在权衡(索引使用存储并且需要维护)。

2. B+树

（计算机基础的经典数据结构，多路查找树）

B+树是一种自平衡的树数据结构，它保持数据的排序，并允许在O(log(N))中进行查找、顺序访问、插入和删除。它针对读/写大数据块的面向磁盘的DBMS进行了优化。

几乎每个支持顺序保持索引的现代DBMS都使用B+树。有一种特定的数据结构称为B-Tree，但人们也使用这个术语来泛指一类数据结构。现代B+树实现结合了其他B-Tree变体的功能，例如B^link-Tree中使用的同级指针。

形式上，B+树是具有以下属性的 M-Way 查找树：

• 它是完全平衡的(即，每个叶节点都在相同的深度)；
• 除根节点外的每个内部节点至少半满( M/2−1<= key 的个数 <= M−1)；
• 每个有 k 个 key 的内部节点都有 k+1 个非空子节点。

B+树中的每个节点都包含一个 key/value 对的数组：

• 每个节点的数组(几乎)都是按 key 排序的。
• 内部节点的 value 数组将包含指向其他节点的指针。
• 叶子节点 value 的两种方法：1）record IDs：指向 tuple 位置的指针；2）tuple 数据：存储在叶节点中的元组的实际内容。

2.1. 插入 Insertion

找到正确的叶子节点 L
按排序将新条目添加到 L 中：如果 L 有足够的空间，则操作完成；否则，将 L 分成两个节点 L 和 L2。重新均匀分配条目并复制 中间 keys。将指向 L2 的索引项插入 L 的父节点。
要拆分内部节点，请均匀重新分配条目，但 push up 中间 keys。

2.2. 删除 Deletion

找到正确的叶L
移除条目：如果 L 至少已半满，则操作完成。否则，你可以尝试重新分配，从兄弟姐妹那里借。如果重新分配失败，则合并同级。
如果发生合并，则必须删除父项中指向 L 的条目。

3. B+树设计策略

节点大小：

• B+树的最佳节点大小取决于磁盘速度。其想法是通过尽可能多的键/值对来分摊将节点从磁盘读入内存的成本。
• 磁盘越慢，理想的节点应越大（目的是减少磁盘I/O）。
• 与拥有更多单 key 查找相比，某些工作负载的扫描负担可能更重。

合并阈值：

• 某些DBMS在半满时并不总是合并。
• 延迟合并操作可能会减少重组的数量。
• 对于DBMS来说，让 underflows 发生，然后定期重建整个树以重新平衡它可能会更好。

可变长度键：

• 指针 Pointers：将键存储为指向元组属性的指针(很少使用)。
• 可变长度节点：B+树中每个节点的大小可能不同，但需要仔细的内存管理。这种做法也很少见。
• 键映射 Key Map：在节点中嵌入映射到key+value 列表的指针数组。这类似于前面讨论的slotted 页面。这是最常见的方法。

非唯一索引：

• 重复键：使用相同的叶子节点布局，但多次存储重复键。

• 值列表：每个键只存储一次，并维护唯一值的链接列表。
  节点内查找：

• 线性：从头到尾扫描节点中的 键/值 条目。当你找到你要找的 key 时，停下来。这不需要对键/值条目进行预排序。

• 二分：跳到中间 key，然后根据中间关键字小于还是大于搜索关键字向左/向右旋转。这需要对键/值条目进行预排序。

• 插值 Interpolation：根据节点中已知的 低/高 关键字值，近似计算搜索关键字的起始位置。然后从该位置执行线性扫描。这需要对键/值条目进行预排序。

4. B+树优化

前缀压缩 Prefix Compression:

• 同一叶节点中的排序关键字可能具有相同的前缀。
• 不是每次都存储整个key，而是提取公共前缀，只存储每个key的唯一后缀。

后缀截断 Suffix Truncation：

• 内部节点的 Key 只用于流量导向( direct traffic )，我们并不需要整个Key。
• 存储将探测正确路由到索引所需的最小前缀。

批量插入 Bulk Inserts:
提前拥有这批数据的所有 keys。

• 从头开始构建B+树的最快方法是首先对 key 进行排序，然后自下而上构建索引。
• 这比逐个插入要快，因为没有拆分或合并。

pointer swizzling：

• 遍历时需要去buffer pool管理器，让其将page id转换为指针，这样的开销太大
• 保存page id时⽤page指针来替换，写出到磁盘时再将page指针换成page id
• 指针重排是将基于名称或位置的引用转换为直接指针引用（内存地址）

虽然看的课是Fall 2019的课，但由于Fall 2019的GradeScope打分已停止，这里做的是 Fall 2023 的项目。

由于迟先生的加入，从Fall 2022开始，CMU 15-445的Project有了较大的改版，难度也提升了。

1. 环境搭建

• Windows11+WSL2+Ubantu 22.04
• bustub (2023 Fall)
• VScode + Clang + CMake

2. 实现

Slides
Notes

Tips

大部分内容就是数据结构中哈希表的内容，结合数据结构和数据库的实现好理解很多。

1. 数据结构

DBMS对系统内部的许多不同部分使用各种数据结构：

• Internal Meta-Data（内部元数据）：跟踪有关数据库和系统状态的信息。
• Core Data Storage （核心数据存储）：可用作数据库中元组的基本存储。
• Temporary Data Structures（临时数据结构）：DBMS可以在处理查询时动态构建数据结构，以加快执行速度(例如，用于 joins 的哈希表)。
• Table Indexes（表索引）：辅助数据结构，使查找特定元组更容易。

设计决策：

• 数据组织：我们如何布局内存以及在数据结构中存储哪些信息。
• 并发性：如何让多线程不出问题地访问数据结构。

2. 哈希表

哈希表实现了将 key 映射到 value 的关联数组抽象数据类型。它提供了平均O(1)的计算复杂度（时间）和O(n)的存储复杂度（空间）。

哈希表实现由两部分组成：

• 哈希函数：如何将大的密钥空间映射到较小的域中。它用于计算存储桶或槽数组的索引。需要考虑快速执行和冲突率之间的权衡。
• 哈希方案：如何处理散列后的密钥冲突。需要考虑分配大型哈希表以减少冲突与执行额外指令以查找/插入键之间的权衡。

3. 哈希函数

哈希函数接受任何 key 作为其输入。然后，它返回该 key 的整数表示(即,“hash”)。函数的输出是确定性的(即，相同的键应该始终生成相同的散列输出)。

DBMS不想使用密码散列函数(例如，SHA-256)，因为我们不需要担心保护密钥的内容。这些散列函数主要由DBMS内部使用，因此信息不会泄漏到系统之外。对于本课，我们只关心散列函数的速度和冲突率。目前最先进的散列函数是Facebook XXHash3。

Tips1:

加密常见Hash:

• SHA-256
• MD5(2004年被山大王小云老师破解)

数据库常见Hash：

• CRC-64(1975)
• MurmurHash(2008)
• Google CityHash(2011)
• Facebook XXHash(2012)
• Google FarmHash(2014)

Tips2:

不要自己写哈希，浪费时间，直接拿来用

4. 静态（Static）哈希方案

静态哈希方案是其中哈希表的大小是固定的方案。这意味着如果DBMS耗尽了哈希表中的存储空间，则它必须使用更大的表从头开始重建它。通常，新哈希表的大小是原始哈希表的2倍。（我们已知哈希表的大小，且不动态增长。）

为了减少浪费比较的次数，重要的是要避免碰撞×散列key。这需要具有两倍于预期元素数量的段数的哈希表。

4.1. Linear Probe Hashing

线性探针哈希，这是最基本的 hashing 方案。它通常也是最快的。它使用单一的槽表。哈希函数允许DBMS快速跳转到 slots 并查找所需的 key 。（其实就是开放地址法）

• 通过线性搜索表中的下一个空闲插槽来解决冲突；
• 要查看值是否存在，请使用散列转到 slot ，并扫描 key 。如果找到所需的 key 或遇到空 slot ，扫描将停止。

  删除时添加⼀个tombstone(墓碑)标记

4.2. Robin Hood Hashing

这是线性探测散列的扩展，它寻求减少每个 key 从它们在哈希表中的最佳位置的最大距离。允许线程从“rich”keys 中窃取slot，并将它们分配给“poor”keys。

• 每个 key 跟踪它们在表中从其最佳位置开始的位置的数量。
• 插入时，如果第一个 key 比第二个 key 离其最佳位置的距离更远，则一个 key 将占据另一个 key 的槽。然后，必须将删除的 key 重新插入到表中。

4.3. Cuckoo Hashing

这种方法不是使用单个哈希表，而是使用不同的哈希函数维护多个哈希表。哈希函数是相同的算法(例如，XXHash、CityHash)；它们通过使用不同的 seeds 为相同的 key 生成不同的哈希。

• 在插入时，检查每一张表，并挑选任何有空位的 slot 。
• 如果没有表有空闲的 slot ，则从其中一个表中取出元素，并对其进行重新 hash 以找到新的位置。
• 如果我们找到一个循环，那么我们可以用新的hash函数 seeds 重建所有hash表(不太常见)，或者使用更大的表重建hash表(更常见)。

5. 动态（Dynamic）哈希方案

静态散列方案要求DBMS知道它想要存储的元素的数量n。否则，如果需要增大/缩小大小，它将重新构建该表。

动态哈希方案能够按需调整哈希表的大小，而无需重新构建整个表。这些方案以不同的方式执行调整大小的操作，这些方式可以最大化读取或写入。

5.1. 链式哈希 Chained Hashing

这是最常见的动态散列方案。DBMS为哈希表中的每个 slot 维护 桶buckets 的链接列表。

• 通过将具有相同hash key 的元素放入同一 buckets 来解决冲突。
• 如果 buckets 已满，则向链中添加另一个buckets 。哈希表可以无限增长，因为DBMS不断添加新的 buckets 。

5.2. 可扩展哈希 Extendible Hashing

链式散列的改进变体，它拆分 buckets ，而不是让链永远增长。该方法允许哈希表中的多个槽位置指向相同的桶链。

重新平衡哈希表背后的核心思想是在拆分时移动 buckets 条目，并增加要检查以在哈希表中查找条目的 bits 数。这意味着DBMS只需在拆分链的 buckets 内移动数据；所有其他 buckets 保持不变。

• DBMS维护全局和局部深度 bit 计数，以确定在槽数组中查找桶所需的 bit 数。
• 当 buckets 满时，DBMS拆分 buckets 并重新洗牌其元素。如果拆分 buckets 的局部深度小于全局深度，则新buckets 只是添加到现有槽数组中。否则，DBMS会将槽数组的大小增加一倍以容纳新的 buckets ，并递增全局深度计数器。

5.3. 线性哈希 Linear Hashing

该方案不是在桶溢出时立即拆分桶，而是维护一个拆分指针来跟踪下一个要拆分的桶。无论该指针是否指向溢出的桶，DBMS总是拆分。溢出标准由实现决定。

• 当任何桶溢出时，通过添加新的槽条目在指针位置拆分桶，并创建新的散列函数。
• 如果散列函数映射到先前由指针指向的槽，则应用新的散列函数。
• 当指针到达最后一个槽时，删除原有的散列函数，代之以新的散列函数。

Slides
Notes

Tips

这部分与操作系统和计组内容有共通之处，结合会更好理解。

1. 两种锁定义 - Locks vs. Latches

在讨论DBMS如何保护其内部元素时，我们需要区分锁 Locks 和latches。

Locks

• 保护数据库逻辑内容(例如，元组、表、数据库)不受其他事务的影响。
• 在事务持续时间内执行。
• 需要能够回滚更改。
  （笔者把它理解为逻辑的、抽象的、high-level的概念）

Latches

• 保护DBMS的内部数据结构的临界区不受其他线程的影响。
• 在操作持续时间内执行。
• 无需能够回滚更改。
  （笔者把他理解为具体的、low-level的概念，真正对资源进行加锁。类似 Mutex ）

2. 缓冲池 Buffer Pool

缓冲池 是(从磁盘读取的) pages 的内存缓存。DBMS总是想知道得更清楚，所以我们希望自己管理内存和分页，而不是交给操作系统OS。

它是组织为固定大小 pages 数组的内存区域。里面的每个数组条目称为一个 frame。当DBMS请求页时，会将一个完全相同的副本放入其中一个框架中。（frame，对于磁盘的 page来说：slot array；对于缓冲池来说：page）

由缓冲池维护的元数据：

• 页表 Page Table：内存中的hash表，跟踪当前内存中的页面。它将 page ids 映射到缓冲池中的 frame 位置。
• 脏标志 Dirty-flag：线程在修改 page 时设置此标志。这向存储管理器指示必须将该页写回磁盘。
• 引用计数 Pin Counter：跟踪当前正在访问该页面(读取或修改该页面)的线程数量。线程在访问页面之前必须递增计数器。如果页面的计数大于0，则不允许存储管理器将该页面从内存中踢出，否则页面可以被踢出内存。

优化方法：

• 多缓冲池 Multiple Buffer Pools：DBMS还可以有多个用于不同目的的缓冲池。这有助于减少 latch 争用并改进局部性；
• 预取 Pre-Fetching：DBMS还可以通过基于查询计划预取页面来进行优化。在按顺序访问页面时通常这样做；
• 扫描共享 Scan Sharing：查询游标可以连接到其他游标并一起扫描页面。

分配策略：

• 全局策略：DBM应如何为所有活动 txns 做出决策。
• 局部策略：将 frame 分配给特定的txns，而不考虑并发 txns 的行为。

3. 替换策略 Replacement Policies

替换策略是DBMS实现的一种算法，它决定在缓冲池需要空间时从缓冲池中换出哪些pages。

实现目标：

• 正确性 Correctness
• 准确度 Accuracy
• 速度
• 元数据开销

LRU 最近最少使用算法

学过 OS 的一定非常熟悉，没错就是那一套OS页面置换算法。只需要注意下面两点：

维护上次访问每个页面的时间戳。
DBMS选择踢出具有最旧时间戳的页面。

CLOCK 时钟算法

也是 OS 的算法，对LRU算法进行改进，属于LRU的近似算法，每页不需要单独的时间戳。

• 每个页面都有一个引用位 reference bit
• 当页面被访问时，设置为1

用“时钟指针”在环形缓冲区中组织页面：

• 扫描时检查 pages bit 是否设置为1
• 如果是，则设置为0，如果否，则踢出内存
• 时钟指针踢出之间的位置

额外一提：

LRU 和 clock 更换策略存在问题：

• LRU 和 clock 容易受到顺序泛洪 sequential flooding 的影响，在这种情况下，缓冲池的内容会因顺序扫描而被丢弃。
• LRU 页面 实际上可能很重要，因为它不跟踪 页面使用情况的元数据。

更好的解决方法：

• LRU-K：考虑最近K次引用的历史。（LRU是考虑最近的一次）
• 优先级提示 Priority hints：允许txns告诉缓冲池页面是否重要
• Localization：根据每个txn/查询 选择要逐出的页面。

Slides
Notes

1. 数据表示

​ 元组的数据本质上只是字节数组。这取决于DBMS知道如何解释这些字节来派生属性值。数据表示模式是DBMS存储值的字节的方式。

​ 可以存储在元组中的主要类型有四种：整数(integers)、可变精度数字(variable precision numbers)、定点精度数字(fixed point precision numbers)、可变长度值(variable length values)和日期/时间(dates/times)。

整数

• 大多数DBMS使用IEEE-754标准指定的“原生”C/C++类型存储整数。这些值是固定长度。
• 示例：INTEGER、BIGINT、SMALLINT、TINYINT。

可变精度数字

• 使用IEEE-754标准指定的“本机”C/C++类型的不精确、变精度的数值类型。这些值也是固定长度。
• 可变精度数字比arbitrary精度数字计算速度更快，因为CPU可以直接对其执行指令。·例子：FLOAT, REAL。

定点精度数字

• 这些是具有arbitrary精度和小数位数的数值数据类型。它们通常存储在精确的、可变长度的二进制表示中，并带有附加的元数据，这些元数据将告诉系统小数应该在哪里等信息。
• 在舍入误差不可接受的情况下使用这些数据类型，但DBMS会为获得这种精度而付出性能代价。·示例：NUMERIC, DECIMAL。

可变长度数据：

• 任意长度的字节数组
• 有一个header，可以跟踪字符串的长度，以便轻松跳到下一个值。
• 大多数DBMS不允许元组超过单个页面的大小，因此它们通过在溢出页面上写入值并让元组包含对该页面的引用来解决这个问题。
• 有些系统允许您将这些大值存储在外部文件中，然后元组将包含指向该文件的指针。例如，如果我们的数据库存储照片信息，我们可以将照片存储在外部文件中，而不是让它们在DBMS中占用大量空间。这样做的一个缺点是DBMS不能操作该文件的内容。PostgreSQL: TOAST表
• 示例：VARCHAR、VARBINARY、TEXT、BLOB。

日期与时间：

• 通常，这些数字表示为自Unix时代以来的(微/毫秒)秒数。

• 示例：TIME, DATE, TIMESTAMP。

系统目录—System Catalogs：

​ 为了使DBMS能够读取这些值，它维护一个内部目录来告诉它有关数据库的元数据。元数据将包含数据库有哪些表和列，以及它们的类型和值的排序。

​ 大多数DBMS以用于其表的格式将其目录存储在其内部。

2. Workloads

OLTP: On-line Transaction Processing 联机事务处理

• 快速、运行时间短的操作
• 一次对单个实体执行查询
• Write操作多于read操作
• 重复操作
• 通常是人们首先构建的应用程序
• 示例：用户调用Amazon。他们可以向购物车添加东西，也可以购物，但这些操作只会影响他们的账户。
• 倾向考虑行存储模型

OLAP: On-line Analyitical Processing 联机分析处理

• 长时间运行的更复杂的查询
• Reads 数据库的大部分
• 探索性查询
• 从OLTP端收集的数据派生新数据
• 示例：计算这些地理位置在一个月内购买最多的五项商品。
• 倾向考虑列存储模型

3. 存储模型(Storge Models)

​ 在页面中存储元组有不同的方法。到目前为止，我们假设了 n-ary storage model。

N-Ary Storage Model (NSM)

​ DBMS连续存储单个元组的所有属性，因此NSM也称为“行存储”。这种方法非常适合于事务往往只操作单个实体并插入繁重 workloads（我可以理解为：高并发 吗？）的 OLTP Workloads。它是理想的，因为它只需一次提取即可获得单个元组的所有属性。

优点：

• 快速插入、更新和删除 操作。
• 适用于需要整个元组的查询。

缺点：

• 不适用于扫描表的大部分和/或属性子集。这是因为它会获取处理查询不需要的数据，从而污染了缓冲池。

组织NSM数据库有两种不同的方法：

• 堆组织的表 Heap-Organized Tables：元组存储在称为堆的块中，堆不一定定义顺序。
• 按索引组织的表Index-Organized Tables：元组存储在主键索引本身中，但不同于聚类索引。

分解存储模型 Decomposition Storage Model (DSM)

​ DBMS将所有元组的单个属性(列)连续存储在数据块中。也称为“列存储”。此模型非常适合OLAP工作负载workloads，其中只读查询对表属性的子集执行大型扫描。

优点：

• 减少查询执行过程中浪费的工作量，因为DBMS只读取该查询所需的数据。

• 启用更好的压缩，因为同一属性的所有值都是连续存储的。

  缺点：

• 由于元组拆分/缝合，点查询、插入、更新和删除的速度较慢。

要在使用列存储时将元组重新组合在一起，我们可以使用：

• 定长偏移量 Fixed-length offsets：首先假设属性都是定长的。然后，当系统需要特定元组的属性时，它知道如何跳到文件中的那个位置。为了适应可变长度的字段，系统可以填充它们，使它们都具有相同的长度，或者您可以使用一个字典，该字典接受固定大小的整数并将该整数映射到该值。
• 嵌入的元组ID Embedded Tuple Ids：对于列中的每个属性，将元组ID与其一起存储。系统还需要额外的信息来告诉它如何跳到具有该ID的每个属性。总之，这个几乎没啥用了，因为太耗费资源了。

大多数DBMS使用定长偏移量 Fixed-length offsets。

行存储通常更适合于OLTP，而列存储通常更适合于OLAP。

Slides
Notes

Notes已经很详细，仅整理大纲和要点。

1. 存储(Storage)

重点关注“面向磁盘”的 DBMS 架构，该架构假设数据库的主要存储位置位于非易失性磁盘上。

易失性设备（Volatile Devices）：

• 字节寻址随机访问。
• 称为“内存”。

非易失性设备（Non-Volatile Devices）：

• 块/页可寻址的。这意味着，为了读取特定偏移处的值，程序首先必须将 4 KB 页加载到保存程序想要读取的值的内存中。

• 传统上更适合顺序访问（同时读取多个数据块）。

• 称为“磁盘”。不区分SSD或HDD。

2. 面向磁盘的DBMS概括(Disk-Oriented DBMS Overview)

数据库都在磁盘上，数据库文件中的数据被组织成页，第一页是目录页。为了对数据进行操作，DBMS需要将数据放入内存。它通过使用一个缓冲池来管理磁盘和内存之间的来回移动来实现这一点。DBMS还具有执行查询的执行引擎。执行引擎将向缓冲池请求特定页面，而缓冲池将负责将该页面放入内存，并为执行引擎提供指向内存中该页面的指针。当执行引擎在该内存上操作时，缓冲池管理器将确保页面在那里。

3. DBMS vs. OS

4. 文件存储(File Storage)

在其最基本的形式中，DBMS将数据库存储为磁盘上的文件。一些可能使用文件层次结构，其他可能使用单个文件(例如，SQLite)。

​ 操作系统对这些文件的内容一无所知。只有DBMS知道如何解密它们的内容，因为它是以特定于DBMS的方式编码的。

​ DBMS存储管理器负责管理数据库的文件。它将文件表示为页面集合。它还跟踪哪些数据已被读取和写入页面，以及页面中有多少可用空间。

5. 数据库页(Database Pages)

DBMS将数据库组织成固定大小的数据块(称为页面)中的一个或多个文件。页面可以包含不同类型的数据(元组、索引等)。大多数系统不会在页面中混合使用这些类型。一些系统将要求它是自包含(self-contained)的，这意味着 read 每个页面所需的所有信息都在页面本身上。

6. 数据库堆(Database Heap)

有几种方法可以找到DBMS想要的页面在磁盘上的位置，堆文件组织就是其中之一。堆文件是以随机顺序存储元组的无序页面集合。

7. 页面布局（Page Layout）

每个页面都包含一个header，记录有关页面内容的元数据，即描述数据的数据（data about data），主要是描述数据属性（property）的信息，用来支持如指示存储位置、历史数据、资源查找、文件记录等功能）

8. 元组布局(Tuple Layout)

​ 元组本质上是一个字节序列。DBMS的工作是将这些字节解释为属性类型和值。

【bilibili】五分钟学设计模式

什么是设计模式？

设计模式（Design pattern）是软件开发人员在软件开发过程中面临的一般问题的解决方案。使用设计模式是为了重用代码、让代码更容易被他人理解、保证代码可靠性。

设计模式的类型

一般意义上，共有 23 种设计模式。这些模式可以分为三大类

• 创建型模式（Creational Patterns）提供了一种在创建对象的同时隐藏创建逻辑的方式，而不是使用 new 运算符直接实例化对象。这使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活。
• 结构型模式（Structural Patterns）关注对象之间的组合和关系，旨在解决如何构建灵活且可复用的类和对象结构。
• 行为型模式（Behavioral Patterns）关注对象之间的通信和交互，旨在解决对象之间的责任分配和算法的封装。

当然，我们还会讨论另一类设计模式：J2EE 设计模式。

创建型模式

1. 单例模式（Singleton Pattern）
2. 工厂模式（Factory Pattern）
3. 抽象工厂模式（Abstract Factory Pattern）
4. 生成器模式/建造者模式（Builder Pattern）
5. 原型模式（Prototype Pattern）

结构型模式

1. 装饰器模式（Decorator Pattern）
2. 适配器模式（Adapter Pattern）
3. 外观模式（Facade Pattern）
4. 状态模式（State Pattern）
5. 代理模式（Proxy Pattern）
6. 享元模式（Flyweight Pattern）
7. 组合模式（Composite Pattern）
8. 桥接模式（Bridge Pattern）

行为型模式

1. 观察者模式（Observer Pattern）
2. 策略模式（Strategy Pattern）
3. 责任链模式（Chain of Responsibility Pattern）
4. 模板模式（Template Pattern）
5. 命令模式（Command Pattern）
6. 备忘录模式（Memento Pattern）
7. 迭代器模式（Iterator Pattern）
8. 中介者模式（Mediator Pattern）
9. 访问者模式（Visitor Pattern）
10. 解释器模式（Interpreter Pattern）

设计模式的原则

1. 开闭原则（Open Close Principle）实现热插拔，提高扩展性。

2. 里氏代换原则（Liskov Substitution Principle）实现抽象的规范，实现子父类互相替换；

3. 依赖倒转原则（Dependence Inversion Principle）针对接口编程，实现开闭原则的基础；

4. 接口隔离原则（Interface Segregation Principle）降低耦合度，接口单独设计，互相隔离；

5. 迪米特法则（Demeter Principle）又称最少知道原则：功能模块尽量独立；

6. 合成复用原则（Composite Reuse Principle）尽量使用聚合，组合，而不是继承；

维护一个存储下标的单调栈，入栈时确定左边界，出栈时确定右边界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int n=heights.size();
        vector<int> left(n);
        vector<int> right(n,n);

        int ans=0;

        int i=0;
        while(i<n){
            while(!s.empty()>0 && heights[s.top()]>heights[i]){
                right[s.top()]=i;
                s.pop();
            }
            left[i]=s.empty()?-1:s.top();
            s.push(i);
            i++;
        }

        int j=0;
        while(j<n){
            ans=max( ans , (right[j]-left[j]-1) * heights[j] );
            j++;
        }
        return ans;
    }
};