lec8 Btreefor indexesagendaBtree overview, design choices, optimizationsB trees什么是 B树B树是一种自我平衡的、有序的(m) 路搜索树。(m) 路(m)-way指的是树的分叉数Fanout。不同于二叉树只有 2 个子节点B树可以有成百上千个子节点。复杂度搜索、顺序访问、插入和删除的时间复杂度均为 (O(\log_m n))。因为 (m) 通常很大所以树的高度非常低查询速度极快。特点完全平衡Perfectly Balanced所有的叶子节点Leaf Nodes都处于相同的深度。这意味着无论你查找哪个数据经过的路径长度都是一样的性能非常稳定。半满规则Half-full为了保证树的饱满度除了根节点外每个节点至少要保持“半满”状态。键Keys的数量范围(\lceil m/2 \rceil - 1 \le \text{#keys} \le m-1)。这个设计是为了防止空间浪费并减少树的层数。子节点比例如果一个内部节点有 (k) 个键那么它必须有(k1)个非空子节点。键起到的是“分界线”的作用引导搜索走向正确的子节点。针对大块数据优化这是 B树最重要的实际意义。它专门为磁盘读取/写入大块数据而优化。由于 (m) 很大树会变得很“矮胖”这意味着找到数据所需的磁盘 I/O输入/输出操作次数非常少。现实实现不一定严格遵守B树相比于 B 树B-Tree有两个显著改进数据只存在于叶子节点内部节点只存索引不存实际数据这样一行能放更多索引分叉数 (m) 更大。非叶节点(node*keykey用于指示查找方向),叶子节点(keyvalue)叶子节点链表叶子节点之间通常有指针相连图中提到的 Sequential Access这使得范围查询比如查找 ID 在 10 到 100 之间的数据非常快。节点规则键/值对数组Key/Value Pairs每一个 B树节点本质上都是一个数组数组中的每个元素都是一对{Key, Value}。键 (Keys)来源于你创建索引的列比如用户的 ID、订单号等。它们用于在树中进行导航和比较。值 (Values)这是区分节点类型的核心。根据节点身份的不同存储的内容完全不同内部节点 (Inner Nodes)存储的是指向子节点的指针Page ID / Pointer。它告诉搜索算法“如果你找的值在这个区间请往这个子节点走”。叶子节点 (Leaf Nodes)存储的是实际的数据。通常是“记录 IDRecord ID”或者是“整行数据Row Data”。有序存储Sorted Key Order节点内的数组通常是按键Key的大小顺序排列的。原因只有保持有序程序才能在一个节点内部使用二分查找Binary Search。效率如果一个节点很大例如包含几百个键有序排列能让节点内的搜索速度从 (O(n)) 降低到 (O(\log n))。NULL 值的处理Store all NULL keys...这是一个关于数据库实现细节的规定所有的 NULL 值必须统一存放在最左边第一个或最右边最后一个叶子节点。为什么要这么做为了保持树的连续性。NULL 在 SQL 中通常被认为比任何值都小或者都大取决于数据库实现。这样在进行范围查询Range Scan时数据库可以非常方便地跳过或者直接包含所有的空值。OperationInsert基础插入流程寻找位置首先从根节点开始向下遍历找到该数据应该存放的叶子节点 (L)。按序插入将数据项Key/Value放入 (L) 中并保持节点的有序性。检查空间如果 (L) 还有空位插入直接结束这是最理想的情况。如果 (L) 已经满了就需要进行分裂Split。叶子节点的分裂Leaf Split—— “Copy Up”当叶子节点 (L) 溢出时系统会创建一个新节点 (L_{2})平分数据将 (L) 中的数据项平均分配到 (L) 和 (L_{2}) 中。复制索引Copy Up将 (L_{2}) 中的最小键值复制一份插入到父节点中作为索引。逻辑为什么要用“复制Copy”因为 B树的所有实际数据都必须完整地保存在叶子节点中所以这个键既要在父节点当“路标”也必须留在叶子节点当“数据”。内部节点的分裂Inner Node Split—— “Push Up”如果父节点内部节点也满了它也需要分裂平分键值同样将键值平分到两个内部节点中。提升索引Push Up将中间的那个键直接提取Push到更高层的父节点中。逻辑为什么要用“提升Push”因为内部节点只负责导航不需要存储实际数据。这个键被提拔到上一层后不需要留在当前层。Delete查找并删除定位从根节点开始搜索找到该数据项所在的叶子节点 (L)。执行直接从 (L) 中移除该条目entry。检查“半满”规则 (The Half-full Rule)这是删除操作的核心。B树要求每个节点除根节点外至少要占用一半的空间。情况 A足够饱满Safe如果删除后(L) 的记录数仍然 (\ge \lceil m/2 \rceil - 1)则删除完成不需要额外操作。情况 B过于空虚Underflow如果删除后(L) 仅剩 (\lceil m/2 \rceil - 1) 个条目甚至更少就触发了Underflow需要通过以下两种手段修复两种修复手段按优先级执行第一种重分配Re-distribute / Borrowing动作尝试从 (L) 的“兄弟节点”同一个父节点的相邻节点那里借一个键值对。结果兄弟节点多匀给 (L) 一个值两个节点都满足半满条件。树的高度不变。要更新父节点索引第二种合并Merge前提如果兄弟节点也快空了借不出值则执行合并。动作将 (L) 和兄弟节点的所有条目合并成一个节点。级联效应因为两个节点变成了一个父节点中原本指向它们的其中一个索引就没用了。必须从父节点中删除该索引。如果父节点删除索引后也变得不满足“半满”规则这个合并过程就会向上递归直到根节点。根节点可以拉下来合并(不半满)如果合并到根节点时根不满。(平时允许根节点不满)composite index联合索引核心逻辑排序顺序联合索引在 B 树中的排列是严格按顺序的。它先按第一列a排序在a相同的情况下再按第二列b排序在a和b都相同的情况下最后按c排序。比喻 就像查纸质电话本。它是先按“姓”排姓一样的再按“名”排。如果你只知道名不知道姓这电话本就没法高效查了。最左前缀原则The Prefix Rule这是理解联合索引最重要的点。图中列出了三种查询情况完全支持(a1 AND b2 AND c3)你提供了所有的前缀数据库可以一路导航到叶子节点效率最高。部分支持(a1 AND b2)虽然没给c但你给了a和b。数据库依然可以利用索引快速定位到所有a1且b2的范围。很少支持或不支持(b2)或(c3)为什么因为索引是先按a排的。如果跳过a直接找b2这些b2的数据可能散落在 B 树的各个角落索引就失去了快速定位的意义。注为什么图中写的是 “Rarely Supported很少支持” 而不是 “Not Supported”因为有些现代数据库有“索引跳跃扫描Index Skip Scan”技术但在大多数情况下这种查询会导致全表扫描。duplicate keys如果在索引列中有大量重复的值比如“城市”或者“性别”列B树该如何处理方案 1拼接记录 IDAppend Record ID这是目前最主流、最优雅的做法。做法既然原始的键Key不唯一那我们就人为地让它变得唯一。数据库会将该行数据唯一的Record ID或者主键 ID拼接到原始键的后面形成一个新的“组合键”。例子假设你要索引“年龄”列有很多人的年龄都是20。数据库在索引内部存储的其实是(20, RecordID_101)、(20, RecordID_205)。优势唯一性所有的键在树中都是唯一的这让插入和删除的逻辑变得非常简单。支持部分匹配就像我们之前聊过的联合索引你依然可以只搜Key20由于 Record ID 是排在后面的B树依然能通过前缀匹配定位到所有年龄为 20 的区间。方案 2溢出叶子节点Overflow Leaf Nodes这种做法比较“暴力”。 不要做做法允许键重复。当一个叶子节点被同一个键值塞满时不进行常规的树分裂而是额外挂载一个溢出页Overflow Page专门用来装这个键对应的后续数据。劣势维护复杂这种结构打破了 B树整齐的层级关系。性能隐患如果某个值极其多例如 100 万行数据都是同一个城市查找这个城市时就会变成在一条长长的溢出链表里进行线性扫描速度极慢。修改麻烦插入和删除时需要额外判断是否操作溢出页。cluster indexes 聚集索引The table is stored in the sorted order speci$ed by the primary key, as either heap- or index-organized storage. Since some DBMSs always use a clustered index, they will automatically make a hidden row id primary key if a table doesn’t have an explicit one, but others cannot use them at all.Index Scan Page Sorting核心问题为什么“按索引顺序找数据”很慢当你使用非聚集索引查找一堆数据时比如WHERE age 20索引本身是有序的你能很快在索引里找到 age 为 21, 22, 23... 的记录。物理存储是乱序的虽然 age 在索引里是挨着的但这些记录在磁盘上的实际位置Page ID可能天差地别。冗余读取Redundant Reads正如图片右侧那堆乱七八糟的红线所示为了拿第一条数据你读了Page 102拿第二条你读了Page 104拿第三条你发现它竟然还在 Page 102。如果不做优化数据库会傻傻地反复加载同一个页面或者在磁盘上跳来跳去进行极其缓慢的随机读取。更好的方案按页 ID 排序A Better Approach图片中给出了解决办法这在很多现代数据库里被称为MRRMulti-Range Read优化先收集不急着读先扫描索引把所有符合条件的记录及其对应的Page ID全部拿到内存里。按物理地址排序重点来了对这些 Page ID 进行排序。比如你原本的读取顺序是(102, 103, 104, 104, 102...)排序后变成(101, 102, 102, 103, 104, 104...)。BTree Design Choicesnode sizeB树节点的大小并不是固定的而是取决于你的数据存在哪儿。核心规律是存储设备越慢节点Node Size就应该越大。merge threshold理论上B 树是“完美平衡”的删一个值就可能引发合并。现实中数据库更倾向于“懒惰策略”。只要树的高度不增加节点稍微空一点是可以接受的。**更好的策略定期重构Periodic Rebuild与其在每次删除时都小心翼翼地维持完美平衡不如容忍一些比较空的节点Underfilled Nodes存在。等到系统空闲时再通过定期重建整个索引Rebuild/Vacuum来统一回收空间。这在大规模并发写入的环境下性能更好。variable-length keys当索引的键Key长度不固定时比如VARCHAR类型的字符串B树该如何高效存储方案 1指针Pointers做法节点里不存真正的字符串只存一个指向该属性实际位置的指针。特点节点的大小变得整齐划一了因为它只存固定长度的指针。应用这种做法在内存数据库如早期的 T-Trees中比较常见。缺点每次比较 Key 时CPU 都要顺着指针去内存别的地方“跳”一下这会造成大量的随机访问对缓存Cache极不友好。方案 2变长节点Variable-Length Nodes做法允许每个索引节点的大小是不一样的根据存的东西多少来定。缺点内存管理噩梦。在磁盘或内存中分配大小不一的块会导致严重的“外部碎片”。比如你想找个 12KB 的空位结果只有一堆 4KB 的散碎空间。方案 3填充Padding做法简单粗暴。如果定义最大长度是 255 字节那么所有 Key 哪怕只有一个字母也统统占用 255 字节剩下的用 0 填充。优点实现最简单计算偏移量极快。缺点空间利用率极低。你会发现索引文件迅速膨胀大部分空间都在存“寂寞”填充符。方案 4键映射 / 间接查找Key Map / Indirection——工业界标准这是目前绝大多数主流数据库如 MySQL, Postgres在节点内部采用的方案也叫Slotted Pages插槽页结构做法在节点的最前面放一个有序的指针数组Key Map。真正的变长 Key 和 Value 倒着从节点的末尾往前塞。优势二分查找因为前面的指针数组是固定长度且有序的你可以对指针做二分查找。空间紧凑Key 之间紧挨着没有填充浪费。灵活这种“目录内容”的结构非常适合管理变长数据。intra-node search节点内搜索当我们通过 B 树的层级结构定位到某一个具体的节点Page后如何在碎如乱麻的键值对数组中以最快的速度找到我们要的那个 Key线性搜索 (Linear Search)现代优化——SIMD二分查找 (Binary Search)插值查找 (Interpolation Search)Optimizationspointer swizzing指针重写它的目的是为了让 B树在内存中运行得像原生数据结构比如 C 的std::map一样快消除掉查表Page Table Lookup的开销。未重写Unswizzled存储的是ID。安全、灵活但每次都要通过中间人Page Table传话。已重写Swizzled存储的是*ptr。极速、直接但维护成本高需要精密的内存追踪机制。write -optimized btree(B^{\epsilon }) 树B-epsilon Tree也被称为分形树Fractal Tree Index。核心秘密在路径上“挖坑” (Log Buffers)传统的 B树就像一个严格的快递员每件包裹数据更新都必须亲自送到收件人叶子节点手里才算完。(B^{\epsilon }) 树的做法在每一个内部节点Inner Nodes里都增加了一个缓冲区Buffer。操作逻辑当你要插入或更新数据时你不需要一路杀到最底层的叶子节点。你只需要把这个“更新指令”丢进从根节点向下遇到的第一个缓冲区里然后就可以告诉用户“好了我写完了”。级联下沉 (Cascading Updates)数据并不是永远停留在缓冲区它们像水一样层层下灌触发条件当一个内部节点的缓冲区填满了它才会把这些数据成批地Batch推送到下一层的子节点中。增量下沉这个过程是“增量”的。数据可能先从第 1 层沉到第 2 层在那儿待一会儿等第 2 层满了再沉到第 3 层最终到达叶子节点。有什么代价权衡之道天下没有免费的午餐它的代价在于读取变复杂了当你查询一个 Key 时你不能只看叶子节点。你必须检查从根节点到叶子节点路径上所有节点的缓冲区看看有没有还没沉下去的最新更新。为了解决这个问题这类数据库通常会配合非常强大的布隆过滤器Bloom Filters来快速判断某个值是否在缓冲区里。