聚集索引数据写入

下面的写入过程原理在 MySQL 和 SQL SERVER 中几乎一样。

假设：

每个页面可以写入 3 条数据 （为了简单，对于根节点和中间节点，我们假设它只能存储三个 key 值）

插入键值对，我们只关注键值

插入的键值及顺序：25，27，15，19，43，40，51，36，58，48，24

根节点的页面号为 100

一，申请一个空页面，该页面也是该表（或者索引）的根节点。

插入 25，27，15， 由于索引是有顺序的，所以存储 15 的时候，会存储到 25 的前面。 

二，写入数据 19，此时，该页面已经没有空间了。需要进行页拆分。

页面拆分的过程如下：

1. 申请一个新页面，假如该页面的编号是 101，

2. 将原来根页面的数据复制到新页面中，同时根页面中的记录全部删除

3. 将根页面的最小指针指向新申请的 101 号页面

4. 至此，根页面分裂完毕，如下图

1. 不要忘记了我们的初心，我们要写入 key 为 19 的数据。key 是 19 的数据，根据 key 的大小，应该写入到 15 和 25 之间，即需要存储到 101 号页面。该页面已经没有空间，所以需要拆分 101 号页面

2. 再次申请一个新页面，假如是 102 号页面

3. 将 101 页面的一半数据移动到 102 号页面，这里需要移动一条数据（key 为 27 的数据）到 102 号页面

4. 101 和 102 页面都在第二层，相互成为兄弟节点，他们需要组成双向链表，以方便全表扫描操作

5. 由于 102 号页面也是根节点（100 号页面）的子节点，父页面需要有指针指向 102 号页面

6. 取 102 页面上的最小的 key 值（key 为 27，不包括数据），复制到 100 页面的 min 指针的后面，该 key 对应的指针指向 102 页面

1. 此时，101 页面终于有空间写入 key 为 19 的数据了，写入之后的树如下图

三，继续写入数据，key 为 43 的数据，key 为 40 的数据，直接写入 102 页面。此时，索引树结构如下图所示

四，接下来，我们写入 key 是 51 的数据，

1. 该值应该放到 102 页面（若有空间的话，应该是最后一行），102 页面已经没有空间，

2. 申请新页面，假如是 103 页面

3. 103 页面和 102 页面做双向链表

4. key 为 51 的数据存储到 103 页面，并且把该 key 复制到根页面，对应的指针指向 103 页面

五，接下来，我们写入 key 是 36 的数据，

1. key 为 36 的数据，应该在 27 和 40 之间，索引应该在 102 号页面

2. 102 号页面已满，所以移动一半数据到 103 页面，即把 key 为 43 的页面迁移到 103 页面

3. key=43 的数据移动到 103 之后，在 103 上是最小的，需要修改 103 父页对应的指针

4. 此时 102 页面就可以存储 key=36 的数据了，写入之后如下图

六，接下来，我们写入 key 是 58 的数据，直接写入到 103 页面

七，接下来，我们写入 key 是 48 的数据，

1. key 为 48，应该写到 43 和 51 之间，即 103 号页面，103 号已满，需要分裂

2. 申请新页面，假如是 104 号页面

3. 把 103 页面上的一半数据，迁移到 104 上，即把 key=58 的数据迁移过去

4. 103 和 104 之间做双向链表

5. 104 上的最小 key 值，写入它的父页面，并且相应的指针指向 104 号页面

6. 此时，103 号页面已有空间存储新数据，直接把 key=48 的页面写入到 103 页面，此时树索引如下：

八，最后，让我们来写入 key 为 24 的数据

1. key 为 24 的数据，需要写到 19 和 25 之间，即 101 页面

2. 101 页面已满，需要分裂

3. 新申请页面，假如是 105 页面

4. 迁移 101 一半的数据（key=25 的数据）到 105 页面

5. 断开 101 和 102 之间的双向链表

6. 添加 101 和 105 之间的双向链表

7. 添加 105 和 102 之间的双向链表

1. 此时复制 105 页面的最小值到它的父节点

2. 此时发现 105 的父节点已满，需要分裂父节点

3. 此时进一步发现 105 的父节点是我们的根节点，

4. 根节点的分裂是：

   申请新页面，假如是 106，把根节点的全部信息移动到 106，

   取 106 页面的最小值放到 106 的父页面，即 100 根页面，并设置相应的指针指向 106

   此时的页面如下图

1. 此时的 105 页面的父节点应该是 106，但是 106 上依然没有空间

2. 分裂 106 页面

3. 新申请页面，假如是 107

4. 移动 106 一半的数据到 107 页面，即 key=58 的 key 移动到 107 页面

5. 添加 106 和 107 之间的双向链表

6. 取 107 页面的最小 key，即 key=58，复制到 107 的父页面（即 100 页面），并做相应的指针指向 107

1. 此时，可以考虑 105 页面的父节点的问题了

2. 105 的父节点应该是 106 页面，索引把 105 上的最小值 key=25 吸入 106 页面，并做指针指向 105 页面

1. 勿忘初心，我们是为了写入 key=24 的值，此时，终于可以在 101 页面写入 24 了。

实际中，一般情况下，索引树到三层的时候，已经可以存储上亿级别的数据了。

这里我们可以粗略的计算下三层能存储多少数据。

加入每行数据平均大小是 200 字节，主键 key 是 4 字节。

对于 SQL SERVER 每个页大小是 8K。

根节点可以存储：8K/4 = 2000 key 值，这也意味着第二层可以有 2000 个页面；

第二层不是叶子层，也只保存 key 值，每个页面也可以存 2000 个 key 值。也就是说第二层的 key 值数量是：2000*2000=400W。也就是说第三层可以有 400W 个页面。

第三层是叶子节点，存储数据，每个页面可以存储 8K/200 = 40 条数据。

则存满第三层的叶子节点，可以存储 400W * 40 = 16000W = 1.6 亿的数据。

对于 MySQL 每个页大小是 16K。

根节点可以存储：16K/4 = 4000 key 值，这也意味着第二层可以有 4000 个页面；

第二层不是叶子层，也只保存 key 值，每个页面也可以存 4000 个 key 值。也就是说第二层的 key 值数量是：4000*4000=1600W。也就是说第三层可以有 1600W 个页面。

第三层是叶子节点，存储数据，每个页面可以存储 16K/200 = 80 条数据。

则存满第三层的叶子节点，可以存储 1600W * 80 = 128000W = 12.8 亿的数据。

以上是粗略计算的数据页面。要是索引页面的话，存储的索引值会更多。毕竟索引相对数据来说，体积更小一些。