目的:将上一节的 B+tree 数据结构 存储在 硬盘
1. 数据表 的 硬盘存储
序列化和反序列化,就是 内存数据结构包装成 bytes -> 写入硬盘,
从硬盘读取 bytes -> 在内存解析成想要的数据结构
当数据存在硬盘时,计算机每次读取 1 page 大小的硬盘空间。
page 存储的数据信息:
下面的 n 为 n_keys = len(keys) 的最大值
节点通用的部分
4 字节 page_number 节点的编号1 字节 leaf:bool
4 字节 存 n_keys,n_keys= len(keys)
4n 字节,keys 每个元素 4 字节,n 是最大容量
9+4n
非叶子节点,children 存的是下一个 节点/page 的 指针/编号
4 字节 存 n_pages,n_pages=len(pages)
中间节点 n_pages 总是要比 n_keys 多 1 个
4n+4 字节,pages 每个元素 4 字节,n+1 是 pages 最大容量
非叶子节点总共
(9+4n) + 4n+8 = 8n+17
叶子节点,children 存的是 行数据/value
4 字节 存 n_values,n_values=len(values)
12n 字节,values 每个元素12 字节,叶子节点,key 和 value 是一一对应的,n 是 values 最大容量
叶子节点总共
(9+4n) + 12n+4 = 16n+13
举例:一个节点
假设 degree 为 3
degree - 1 <= n_keys <= 2 * degree - 1
degree <= n_childrens <= 2 degree
则 n = 5
叶子节点最多会占用 13+165=93 字节
非叶子节点最多占用 17+85=57 字节
为了方便,选 100 字节吧
page_length=100
