04-B树结构的物理实现

1. 二进制编码

• 固定大小，编解码使用相同的字节序

大端：高位在低字节，符合人类习惯
小端：高位在高字节，加法运算方便

encoding - What is the difference between utf8mb4 and utf8 charsets in MySQL? - Stack Overflow

2. 数据库文件物理组织形式通用原理

2.1. 确定寻址方式

1. 文件拆分成大小相同的页(page)，单个块(block)或连续块(multiple block)组成
2. 相同大小的page，目的是简化读取和写入访问，按页写入，从内存写到磁盘

数据存储结构一般分为两类：原地更新、仅追加通常都是按照页进行组织。

数据库的表结构一般是固定的，指定字段的数量、顺序和类型。
元数据放在page的头部。

2.2. 定长：页的结构

顺序的(key,value,pointer)

2.3. 变长

2.3.1. 分槽页（slotted page）

• 前面的指针按顺序，后面具体存值的单元格不按顺序（从后往前放，两块区域相遇说明放满了）

• 实现了：

  1. 最小开销：唯一的额外开销是指针
  2. 空间回收：页的碎片整理和重写
  3. 动态布局：外部只能通过page id引用，确切位置由页内决定

2.3.2. 分页槽的单元格布局（Cell Layout）

2.3.3. 管理变长数据(del/modify)

构建free block，并指向第一个空闲块的指针保存在页头部，并保存可用字节数

• 使用空闲块的策略
  1. 首次适配优先：找到第一个适配的空闲块
  2. 最佳适配优先：找到一个剩余段最小的空闲块

2.4. 版本

1. 文件名带版本前缀
2. 版本使用专门文件存储，postgreSQL存在PG_VERSION
3. 直接存在每一个具体文件（索引）的头部，头部按照不变式编码

2.5. 页头

• 保存关于用于页定位，维护和优化的信息。

  • 包括——页内容和布局的标志位、单元格数量、空闲空间的上界下界的偏移量以及其他
  • PostgreSQL——页大小和布局版本
  • MySQL InnoDB——记录总数、层数和其他一些与实现相关的值
  • SQLite ——单元格的数量和最右指针

• Magic Numbers: 多字节的常量数值

  • 标志：后面是一个page
  • 标识：指定页的类型或者标识其版本
  • 意义：验证页加载和对齐是否正确

2.6. 同级指针 Sibling Links

2.7. 最右指针（Rightmost Pointers）

• B 树拆分子树并进行遍历，指向子页的指针总比键的个数多一个（指针 N+1）
  • 最右指针单独存放，其他键值+指针匹配存放

• 拆分后追加到其父节点上，则必须对最右侧的子指针重新赋值
  

2.8. 节点高键 High Keys

2.9. 溢出页 Overflow Pages

节点大小和树的扇出是固定的 ，不会动态改变

溢出页在B树上没有限制，但是在基本表上有限制

2.10. 二分搜索

带间接指针的⼆分搜索（灰⾊为要搜索 的数据，虚线是通过指针进⾏⼆分搜索， 实线是跟随指针的访问动作

2.11. 分裂与合并

• 分裂与合并都从叶节点发起，向上传递
  • 需要一条从叶节点返回跟节点的路径
• 实现方式：
  1. 功能上实现：用一个栈记录路径
  2. 结构上实现：在页头里放一个指向父节点的指针的字段(引入冗余需要保证一致性)

2.12. 再平衡

• 为了推迟分裂，减少频繁的分裂和合并。

• 再平衡

  1. 提高平均占用率
  2. 但需要额外跟踪和平衡
  3. 更高的利用率意味着更高效的搜索

2.13. 右侧追加

直接往后延

• 自增数值作为主索引的优势在优化方面

  • 所有的插入都在所有的末尾（最右边的叶子），大量的分裂集中在每层的最右边

• 特征，在非自增数值做主索引中应用

  • 批量加载，重新构建（批处理，自下而上构建树，按层写入）
  • 不可变B+树

2.14. 压缩

本质也是一种平衡，访问速度vs压缩率

• 不同粒度下的压缩
  1. 文件压缩，应用在较小的文件
  2. 按页压缩数据
     • 可能会导致跨页读取，增加IO次数
  3. 按记录行/列压缩
     • 对每个行都要解压缩
• 压缩算法选择的基本逻辑
  1. 压缩比、性能和内存开销
  2. 指标：内存开销、压缩性能、解压性能、压缩比

2.15. 维护

• 一个软件系统，除了面向用户的操作之外，还有面向系统本身的操作
  • 维护存储的完整性、回收空间、减少开销和维持Page的有序
  • 后台执行，批处理

2.15.1. 删除

• 基本操作：
  1. 填空
  2. 无法寻址
     

2.15.2. 更新和删除碎片

• 填空null或删除偏移量
  1. 删除偏移量是最常使用的方式，体会一下Page为什么要设置偏移量（分离）
  2. 有些数据库又专门的垃圾收集功能，将删除和更新的单元格留在原处，以便进行多版本控制
  3. 事务完成后，ghost record的数据结构被回收
• 碎片化单元格（fragmented）需要被碎片整理
  1. 重写页面，更新操作对叶节点页面也可以更新偏移量，不重写页面
  2. 碎片整理（compaction、vacuum……）
  3. 更新偏移量、移动新位置、可用磁盘页id进入空闲页列表（freelist）

2.16. 总结

1. 静态：页头、最右指针、高键、溢出页
2. 动态：遍历、间接指针二分搜索、父指针或导航结构
3. 维护：再平衡、右侧追加、批量加载、垃圾收集

密集存储：查询方便
分散存储：写方便

堆文件

3. 数据库具体文件的物理组织形式

本质都是树，结构相同、但取值以及不同动态使用算法的树

1. 顺序文件(索引，B+树等)
2. 散列文件（hash）
   • 纯随机，没有顺序
3. 随机文件（堆文件，基本表结构）
4. 聚簇文件（融合性文件）
   • 按照一定程度的顺序

结构优化
算法优化

4. IOT

Index-orginzed Table

记录强制排序

5. 数据自动分组(grouping)

• 分区(Partition) 也是一种数据分组的方式

  • 把逻辑上的一张基本表分到不同的物理文件上，底层是多张物理表

• 优点

  • 提高并发性和并行性
  • 从而增强系统架构的伸缩性

• 面对两大问题

  1. 管理问题（备份和恢复）
  2. 数据量巨大的表，B+树的索引失效，非聚簇索引的大量随机I/O问题

• 应对策略

  1. 全量扫描数据，不需要任何索引
  2. 索引数据，并分离出热点数据

5.1. 循环分区

如滑动窗口

• 不受数据影响的内部机制
  1. 分区定义为各个磁盘的存储区域
  2. 可以看作是随意散布数据的机制
  3. 保持更改带来的磁盘I/O操作的平衡

5.2. 数据驱动分区

• 根据一个或多个字段的值来定义分区
  • 一般叫分区视图（partitioned view），而MYSQL老版本称为（merge table）
• 实现方式
  1. 哈希分区
  2. 范围分区/键值分区
  3. 列表分区：把记录的某些字段放在某些分区，把热点和非热点分开，每个分区会额外复制主键

5.3. 分区表的底层实现原理

分区表由多个相关的底层表实现
对存储引擎来说，底层表和普通表没有任何区别
分区表的索引是在底层表上各自加上一个完全相同的索引
操作时都有一个分区层打开并锁住所有底层表的过程

5.4. 分区的问题

1. NULL值会使分区过滤无效（PATITION by RANGE COLUMN（order_date））

2. 分区列和索引列不匹配（没有索引，或关联查询时关联条件不匹配索引）

3. 选择分区的成本较高（分区范围的成本需要注意）

4. 打开并锁住所有底层表的成本可能很高（开销和分区类型无关，主键查找单行会带来明显开销）

5. 维护分区成本高

6. 如果不走分区键，很容易造成全表锁或多次相同索引查询。

7. 很难实现分区中关联查询。

8. 索引的复制导致更新复杂，分区层锁定问题。

9. 分区表，隐藏复杂，使得工程师不可控。

5.5. 数据分区的最佳方法

1. partition key尽量均匀分布
2. partition key不能改动

6. 分区、分表、分库

分区和分表的目的都是减少数据库的负担，提高表的增删改查效率。
分区只是一张表中的数据的存储位置发生改变，分表是将一张表分成多张表
分库主要目的是为突破单节点数据库服务器的 I/O 能力限制

6.1. 分区 Partitioning

• 把一张表分成N个区块，逻辑上是一张表，但底层是N个物理区块组成
• 原因：处理大型表，提高查询效率
• 问题：
  1. 分区维护成本高，尤其是数据分布不均匀的时候
  2. NULL值和分区键的选择不当可能导致分区过滤无效
  3. 分区列和索引列不匹配，全表扫描
  4. 选择分区的成本可能很高
  5. 打开并锁住所有底层表的成本可能很高
  6. 索引维护复杂
  7. 不能解决并发问题

6.2. 分表（手搓分区）

• 把一张表按照一定规则分解成N个具有独立空间的实体表
• 系统读写时需要根据定义好的规则得到对应的字表明，然后操作它
• 解决的问题：
  1. 插入数据需要重建的索引减少
  2. 在应用层完成表的选择，读写锁影响的数据量少(不用锁住所有表再选择)
  3. 分表后单表的并发能力提高了，磁盘I/O性能也提高了，写操作效率提高了
  4. 数据分布在不同的文件，磁盘I/O性能提高
• 问题：
  1. 多张表的事务处理和回滚比一张逻辑表复杂得多
  2. 需要业务系统配合迁移升级，工作量大

6.3. 分库

• 解决单个数据节点访问的I/O能力上限，解决数据库扩展性问题

• 问题：

  1. 事务的支持，分库分表，就变成了分布式事务
  2. join时跨库，跨表的问题
  3. 分库分表，读写分离使用了分布式，分布式为了保证强一致性，必然带来延迟，导致性能降低，系统的复杂度变高

• 垂直拆分

  • 将不存在关联关系或者需要join的表可以放在不同的数据库不同的服务器中
  • 按照业务垂直划分。比如：可以按照业务分为资金、会员、订单三个数据库
  • 需要解决的问题：跨数据库的事务、join查询等问题

• 水平拆分

  • 例如，大部分的站点。数据都是和用户有关，那么可以根据用户，将数据按照用户水平拆分
  • 按照规则划分，一般水平分库是在垂直分库之后的。比如每天处理的订单数量是海量的，可以按照一定的规则水平划分
  • 需要解决的问题：数据路由、组装

• 读写分离

  • 对于时效性不高的数据，可以通过读写分离缓解数据库压力
  • 需要解决的问题：在业务上区分哪些业务上是允许一定时间延迟的，以及数据同步问题

7. 全局ID生成算法

1. 自动增长列
   1. 自带功能，有序，性能不错
2. UUID (128位)
3. COMB (组合)
4. Snowflake (雪花)