目的：实现 B+tree 结构的数据存储，增删改查，存储位置是 内存

  1. # db table 1
  2. 1    小红    88
  3. 2    小绿    92
  4. 3    小白    92

1. 数据表 的 数据结构

先看个 简单的 连续存储 数据表：

一张表是一个文件，所有数据是一个数组，连续存储

限定每个字段的长度，输入字符串，转二进制，不够补 0
id 4 字节
name 12 字节
那么一行 16 字节，连续存储。

insert 一行，直接 append 16 字节。
select 一行，直接读 16 字节到内存对比。遍历。
update = select+insert

b+tree 数据表：

  1. 每个节点 node 数据组成是 是 keys 和 children 2个数组

  2. node1 的 大小是有限的，degree 属性决定的
    degree - 1 <= n_key <= 2 * degree - 1
    degree <= n_children <= 2 degree
    我们要尽量保证 size(node1.keys) 不超过「一页」来设置 degree

  3. 叶子节点 和 非叶子节点 是不一样的，叶子节点的 children 是 [value, value, value]，非叶子节点 children 是 [node, node, node]，数据只存在 叶子节点

    insert

    从 0 开始插数据，开始只有一个节点，node1，那么它就是叶子节点，叶子节点 children 存的是行数据 value

若一行数据 “1 小明 24” 存入节点，node1.keys = [1,] node1.children=[“1 小明 24”,]
keys 和 children 的 index 一一对应

分裂
若 keys 大小达到了上限，上线是 degree 决定的，则需要分裂。node_new = new Node()，node_new 是非叶子节点，node_r.children=[node1, node2…]，node_r 的子节点 是 node1 分裂来的，一分为 2
将 node1.keys 中间数 keym 插入 node_r.keys
再将 node1 分右边一半，分为新的 node2 = new Node(), node_r.children=[node1, node2], node_r.keys=[keym]
这就是第一次分裂。层数+1

  1. 之后再添加行，大于 keym 的添加到 node2，小于 keym 的添加到 node1，若是 noder 满了再一分为二，分裂出一个新的非叶子节点 node，就又多了一层。

select

用 id 作为索引，用 id 查询
从根节点往下查，非叶子节点，用 id 对比 keys 查出 index，找到子节点
叶子节点直接用 id 查到 index，找到 value

update


数据存硬盘，叶子节点和 非叶子节点，如果大小不一样，怎么算地址呢？？？这需要分开来算。