CS186 SQL6 B+ Trees

¶写在前面

• 目前看到：

(3) Lec 6 Part 1 Intro to Indexes - YouTube

¶Reminder on Heap Files

• Two access APIs:

  两种从堆文件中查找记录的方式

  • fetch by recordId (pageId, slotId)

    直接通过给定的记录ID来检索特定的记录

    适合快速定位单个记录，尤其是已知道记录的确切位置时

  • scan (starting from some page)

    从文件中的某一页开始，顺序地读取所有记录的过程

    通常用于全表扫描或当查询条件不支持更高效的索引访问时

• Data structures in RAM:

  内存中的数据结构

  • Search trees (Binary, AVL, Red-Black, …)

    可以在不扫描整个数据集的情况下进行查找记录的数据结构：

    搜索树（如二叉搜索树(Binary Search Trees)，AVL树，红黑树(Red-Black Trees)，等等）

    二叉搜索树(Binary Search Trees)：每个节点最多有两个子节点，左子树上的所有节点值小于根节点值，右子树上的所有节点值大于根节点值

    AVL树：一种自平衡的二叉搜索树，任何节点的两个子树的高度最大差别为1

    红黑树(Red-Black Trees)：也是一种自平衡二叉搜索树，通过对树进行染色并在插入和删除时调整树来保持平衡

  • Hash Tables

    散列表(Hash Tables)：通过使用哈希函数将键映射到数组的一个位置上，从而实现快速的数据访问。

• Needed: disk-based data structures

  • “paginated”: made up of disk pages

    由于磁盘访问的时间成本比内存访问高得多，因此磁盘上的数据结构设计通常需要考虑如何最小化磁盘I/O操作。分页技术是将数据划分为固定大小的块（称为页面），以便有效地管理和检索数据

    分页的数据结构使得数据库管理系统能够在磁盘上高效地存储和检索数据，同时尽量减少每次磁盘访问时读取的数据量

¶Index

• An index is data structure that enables fast lookup and modification of data entries by search key

  索引是一种数据结构，它使通过搜索键快速查找和修改\数据条目成为可能

  • Lookup: may support many different operations

    • Equality, 1-d range, 2-d region, …

      等值查询，一维范围查询，二维区域查询等

      等值查询：比如查找某个特定值的所有记录

      一维范围查询：查找在一个特定范围内的记录

      二维区域查询：在地理信息系统中，可能会用到这样的查询来查找落在某个矩形区域内的记录

    • Search Key: any subset of columns in the relation

      搜索键：关系中的任何子集列

      搜索键(Search Key)：这是用来创建索引的一组列

      可以是一个单一的列，也可以是多个列的组合

      搜索键不需要是唯一的，这意味着同一个键值可以在表中有多个匹配项

      • do not need to be unique
        • e.g.:(firstname) or (first name, lastname)

¶Index Part 2

• Data Entries: items stored in the index

  数据条目(Data Entries)：存储在索引中的项目

  • Assume for today: a pair (k, recordId)

    假设一个对(k, recordId)的配对

    键值(k)对应于搜索键，而recordId则是指向实际数据行的指针

    recordId可以帮助快速定位到堆文件中的具体记录

    • Pointers to records in Heap Files

      指向堆文件中记录的指针

    • Easy to generalize later

      后续容易扩展

• Modification: want to support fast insert and delete

  修改(Modification)：希望支持快速插入和删除

  索引的设计需要考虑到如何高效地进行这插入和删除等操作而不影响整体性能

  例如，B+树在插入和删除时可以通过分裂或合并节点来维持树的平衡

• Many Types of indexes exist: B± Tree, Hash, R-Tree, GiST, …

  存在多种类型的索引：B+树、哈希索引、R树、GiST（通用搜索树）等

  B+树(B±Tree)：主要用于支持范围查询和排序。B+树的叶节点包含实际的数据指针，并且叶节点之间互相链接，便于顺序访问

  哈希索引(Hash Index)：适用于等值查询，通过哈希函数直接计算出键值的位置

  R树(R-Tree)：用于空间索引，支持多维数据的范围查询，常见于地理信息系统(GIS)

  GiST（Generalized Search Tree）：这是一个框架，用于构建多种类型的索引，支持复杂的数据结构和查询类型

  选择哪种类型的索引取决于数据的特性和预期的查询模式

¶Simple example

• Step 1: Sort heap file & leave some space

  对堆文件进行排序并留出一些空闲空间

  在创建索引之前，首先需要对堆文件中的记录进行排序

  排序的目的是让具有相似键值的记录彼此靠近，从而提高基于键值的查找效率

  排序时需要预留一些空闲空间，以便将来插入新记录时不需要频繁地重新组织数据

• Step 2: Build the index data structure over this

  建立索引数据结构

  索引结构的选择通常取决于数据的特性以及查询的需求

  • why not use binary search in this heap file

    why not 使用二分搜索

    • Fan-out of 2 → deep tree → lots of I/Os

      扇出度(fan-out)为2 → 树太深 → 大量的I/O操作

      因为每次都需要访问磁盘来获取下一部分数据。这会导致效率低下，尤其是在处理大量数据时

    • Examine entire records just to read key during search

      效率低→在查找过程中为了读取键而遍历所有记录

      使用二分查找，即使只访问记录中的某个特定字段（如搜索键），也需要读取整个记录

      因为记录在磁盘上是以连续的方式存储的，无法直接访问某个字段。这不仅浪费了带宽，也增加了不必要的磁盘I/O操作

¶Build a high fan-out search tree

构建高扇出度的搜索树

• Start example: Sorted (key, page id) file

  起始示例：已排序的(key, page id)文件

  为要搜索的记录文件（堆）构建一个线性的索引文件

  键值和对应的页面ID已经被排序

  意味着，如果有一个键值，我们可以快速定位到相应的页面ID

  • No record data

    不包含记录数据

    索引文件通常不包含完整的记录数据，而是仅包含用于快速查找的键值和指向实际数据所在页面的ID

  • Binary search in the key file. Better.

    在键文件中使用二分查找效率更高

    查找操作只需要关注键值和页面ID，减少了数据传输量，查找效率↑↑

    二分查找对于已排序的文件分成有效，查找速度↑↑↑ ∵每次比较都可排除一半候选范围

  • Forgot: Need to break across pages

    忽略的问题：需要跨越页面进行分割

    在实际的磁盘文件中，数据是分页存储的

    如果一个页面的容量有限，那么一个大的键值范围可能需要分布在多个页面上

    要求索引结构能够有效地处理跨页面的数据

  • **Complexity: ** Still binary search, just a constant factor smaller input

    复杂度：仍然是二分查找，只是输入规模减小了一个常数因子

• **B+树**是一种专门为磁盘存储设计的树形数据结构

  • 高扇出度

    每个节点可以存储多个键值对和指针，树的深度较浅，则每次查找需要访问的磁盘页面较少。

  • 跨页面分割

    B+树可以很好地处理跨页面的数据分割，因为它的设计允许在插入或删除数据时通过节点的分裂和合并来保持树的平衡。

  • 高效的磁盘访问

    B+树的节点通常存储在磁盘的单个页面中，这样可以减少磁盘I/O操作的数量，提高查找效率。

¶Status Check

• Some design goals

  • Fast sequential scan

    快速顺序扫描

    可采取方法：

    链式结构：将记录链接起来，使能够按顺序访问。

    例如，在B+树中，所有叶节点都是通过指针相连的，这样可以支持顺序扫描

    预读机制：在磁盘I/O操作中，预读机制可以提前加载后续的数据页，从而减少磁盘访问延迟

  • High Fan-out

    高扇出度：

    指的是每个节点可包含更多的子节点 / 键值对。

    这样减少树的深度，从而减少查找所需的磁盘I/O操作次数

    可采取方法：

    增加节点容量：每个节点存储更多的键值对，减少树的整体深度。

    优化页面布局：合理安排页面中数据，使能够容纳更多的信息，提高扇出度

  • Support insertion

    支持插入数据

    可采取方法：

    动态调整：插入新记录时，如果某个节点已满，则进行节点分裂，即将节点中的部分数据移动到新的节点中

    自平衡机制：例如，在B+树中，当节点分裂时，分裂产生的新节点会被正确地插入到父节点中，以保持树的平衡。

• ISAM (Indexed Sequential Access Method)

  • 致命弱点：越来越多的溢出页面和链接列表可能占用大部分文件，最终搜索降级为线性搜索，跟没有索引的堆文件没啥两样

¶Recap: ISAM（老idea）

• Data entries in sorted heap file

  ¶数据条目在排序的堆文件中

• High fan-out static tree index

  高扇出度的静态树索引

• Fast search + good locality

  快速搜索和良好的局部性

  • Assuming nothing changes

    假设不变性

• Insert into overflow pages

  插入到溢出页面

  向已排序的堆文件中插入新记录时，如果当前位置的空间不足，ISAM会将新记录插入到溢出页面中

  溢出页面用于存储那些无法立即插入到主文件中的记录。这样做可以避免频繁的页面分裂和重组，从而降低维护成本

¶A Note of Caution

• ISAM is an old-fashioned idea

  ISAM是一种经典的文件组织和访问方法，主要用于在磁盘上高效地存储和检索数据

  ISAM最初设计用于那些数据相对稳定、更新频率较低的应用场景

  • Introduced by IBM in 1960s

  • B+ Trees are usually better

    B+树的优势：

    更好的动态适应性：B+树能够更好地处理数据的动态变化，包括插入和删除操作

    更高的扇出度：每个节点可以存储更多的键值对，从而减少树的深度

    更高效的磁盘访问：B+树的设计考虑了磁盘I/O的优化，能够减少磁盘访问次数

    • Though not always

      B+树good， 但不是所有情况都这样

      对于简单应用程序或小型数据库，ISAM够用

• But it’s a good place to start

  • Simpler than B+ Tree, many of the same ideas

    比B+树简单， 很多概念相似

• Upshot

  • Don’t brag about ISAM on resume

    老技术别写简历

  • Do understand ISAM, and tradeoffs with B+ trees

    但理解ISAM，了解其与B+树之间的权衡（？

¶❤❤B± Tree❤❤

¶Enter the B+ Tree

• Similar to ISAM

  • Same interior node structure

    与ISAM相同的内部节点结构

    • <Key, Page Ptr> pairs with same key invariant

      <Key, Page Ptr>对，具有相同的键不变性

  • Same search routine as before

    与ISAM相同的搜索程序

• Dynamic Tree Index

  B+ 树是一种动态树索引

  • Always Balanced

    B+ Tree面对插入和删除操作也始终保持平衡

  • Support efficient insertion & deletion

    B+ 树支持高效的插入删除操作

    B+树在插入和删除时会自动调整节点，以保持树的平衡

    插入：分裂后的节点会被插入父节点

    删除：删除记录时，若某节点过于稀疏，则可能进行节点合并；合并后节点同样插入父节点，保持树的平衡

    • Grows at root not leaves

      在根部分裂而不是叶节点：

      B+树在插入或删除操作时，通常会在根节点处进行分

      树的高度增长从根节点而不是从叶节点开始

  • “+”? B- Tree that stores data entries in leaves only

    B+树是一种特殊的B树，在叶节点中只存储数据条目

    所有的数据记录都存储在叶节点中，而非叶节点仅存储键值对和指向其他节点的指针

• 缺图：(12) Lecture 6 Part 4 B+ Tree Intro - YouTube 1:13

• Occupancy Invariant

  B+树有占用不变量→保持B+树的平衡性和高效性

  • Each interior node is at least partially full:

    每个内部节点

    • d <= #entries <= 2d

      内部节点的键值数量必须在 d 到 2d 之间

    • d: order of the tree (max fan-out = 2d + 1)

      d: 树的阶数

      阶数为d的树的最大扇出度 = 2d + 1

      每个键值后面都有一个指针指向下一个节点，加上最后一个指针，总共可以有 2d + 1 个子节点。

• Data pages at bottom need not to be stored in logical order

  B+树底层的数据页面不必按逻辑顺序存储

  • Next and prev pointers

    前后指针

• 缺图：(12) Lecture 6 Part 4 B+ Tree Intro - YouTube 2:46 4:00

¶B+ Tree in Practice

B+ Tree在实践中的应用

• Typical order: 1600. Typical fill-factor: 67%

  典型的阶数(order)：1600**。**典型的填充率(fill-factor)：67%

  • average fan-out = 2144

    平均扇出度(fan-out) = 2144

  • (assuming 128 Kbytes pages at 40Bytes per record)

    （假设页面大小为128 KB，每条记录占用40字节）

• At typical capacities

  在典型容量下的高度

  • Height 1:2144^2 = 4,596,736 records
  • Height 2:2144^3 = 9,855,401,984 records

• B+树的高度低，但数据量大

¶Searching the B+ Tree

• Same as ISAM
• Find key = 27
  • Find split on each node (Binary Search)
  • Follow pointer to next node
• 索引：<键key, 指向记录的指针pointer>

¶Insert x into a B+ Tree

• Find the correct leaf

  找到正确的叶子结点

• If there is room in the leaf just add the entry

  • Sort the leaf page by key

¶Inserting x into a B+ Tree: Insert

• Find the correct leaf

  找到正确的叶子结点

  • Split leaf if there is not enough room

    没有足够的空间，就分割叶子结点

• Redistribute entries evenly

重新分配旧的叶子节点

• Fix next / prev pointers

  找到下一个 / 上一个指针，分割旧的叶子节点

• Copy up from leaf the middle key

  创建一个父节点，其将成为一个新的索引条目；该索引条目将指向该节点，并作为分割键

  索引的值取节点内最小值

  然后将新的索引放入原始节点的父节点中

• recursively split index nodes

  递归地将父节点拆分为两半

  • redistribute the rightmost d keys

    重新分配最右边的d

• push up from interior node the middle key

  把分到右拆分结点的最左边的key取出，成为新的根节点

  缺图 (12) Lecture 6 Part 6 - YouTube 3:23

  • Now the last key on left

    原父节点最后一个key就是左拆分结点最左边的key

• 分割父节点时，必须实际分配一个新节点root分裂右侧的父节点；分配一个新的根，树就会增长一级

¶Copy up vs Push up

• Notice：

  在B+树中，当进行插入操作时，可能会导致节点分裂。分裂后，需要将某些条目向上移动到父节点

  具体来说，有两种不同的方式来处理这些条目：复制和推

  1. 复制（Copy up）：
     • 当一个叶节点分裂时，其中一个条目会被复制到父节点中。这个条目通常是最小或最大的键值。
     • 例如，如果叶节点分裂后产生了两个新的叶节点，其中一个叶节点的第一个条目会被复制到父节点中。
  2. 推（Push up）：
     • 当一个内部节点分裂时，中间的键值会被推到父节点中。这个键值用于区分两个新的子节点。
     • 例如，如果内部节点分裂后产生了两个新的内部节点，中间的键值会被推到父节点中，用于区分这两个新的子节点

  • The leaf entry (5) was copied up

    叶节点条目 (5) 被复制到上层

  • The index entry (17) was pushed up

    索引条目 (17) 被推到上层

¶Inserting x into a B+ Tree: Final

• Check invariants

  检查不变量

• Key Invariant:

  键不变量

  键不变量：每个内部节点的键值用于区分其子节点。具体来说，对于每个内部节点 [..., (Kl, Pl), ...]，其中 (Kl, Pl) 表示键值 Kl 和指向子节点 Pl 的指针，必须满足 Kl ≤ K 对于 Pl 子树中的所有键值 K

  • Node[…, (Kl, Pl), …] → Kl <= K for all K in Pl Sub-tree

• Occupancy Invariant

  占用不变量

  占用不变量：每个节点（无论是内部节点还是叶节点）的条目数量必须在 d 和 2d 之间。

  • d 是树的阶数，表示每个节点至少包含 d 个条目。
  • 2d 是每个节点最多可以包含的条目数量

  • d <= # entries <= 2d

¶B+ Tree Insert: Algorithm Sketch

• Find the correct leaf L

  找到正确的要插入的叶子节点

  通过典型的搜索算法来完成

• Put data entry onto L

  将数据条目放到叶子节点 L 上

  • If L has enough space, done

    如果叶子节点 L 有足够的空间（即条目数量不超过 2d），直接将新的条目插入到 L 中

  • Else, must split L (into L and a new node L2)

    如果叶子节点 L 没有足够的空间（即条目数量超过 2d），则需要分裂 L

    • Redistribute entries evenly, copy up middle key

      均匀重新分配条目：将 L 中的条目均匀地重新分配到两个新的节点中，即 L 和新的节点 L2。

      复制中间键：将中间的键值复制到父节点中。这个中间键值用于区分两个新的子节点。

    • Insert index entry pointing to L2 into parent of L

      插入索引条目：在 L 的父节点中插入一个新的索引条目，该条目指向新的节点 L2