本篇文章来自 YouTube 上的一个视频, 觉得讲得相对不错. 链接如下: https://www.youtube.com/watch?v=aZjYr87r1b8
目录
disk 结构
disk 是如何存储数据的
什么是索引
什么是多级索引
m-way 搜索树
B 树: m-way 搜索树 + 规则
B 树中的插入操作
B + 树
disk 结构
简单来说: 按照时钟方向分, disk 由很多个 sector 组成, 编号为 0-N. 按照从外到内分, disk 又由多个 track 组成, 编号为 0-N.sector 和 track 交叉的地方, 叫做 block, 每个 block 有自己的 address, 可以用 (track_no,sector_no) 表示. 每个 block 的大小是一样的, 具体的大小要看实际情况, 在这里, 我们假设一个 block 的大小是 512bytes.
需要十分明确的一点是: 无论是读操作, 还是写操作, 都是以 block 为单位进行的.
在 block 内部, 可以看作是一个数组结构, 坐标从 0 到 511. 每个 byte 都有一个 address, 这个称为 offset. 所以我们可以把 disk 上的每一个 byte 用 (track_no,sector_no,offset) 的形式表示.
在计算机中, disk 的结构可以这么简要地表示.
其中有一个读写头, 每个时刻, 读写头对准了 disk 上的其中一个 block(track_no,sector_no). 通过旋转, 可以改变 sector_no, 通过伸缩读写头, 可以改变 track_no.
还有一点, 也是需要明确的:** 只有 disk 上的数据被加载到 RAM(random access memory), 才能被程序使用.** 或者说, 才是真正对程序有用的.
如何优化 RAM 中数据的效率, 这门学问叫做数据结构; 如何优化 disk 中数据的效率, 这门学问叫做 DBMS, 也就是大部分数据库所要研究的内容.
disk 是如何存储数据 (特值定数据库数据) 的
现在有一个 employee table, 其中有这些字段, 每个字段的大小如图所示, 一个 record 的大小总计为 128 bytes.
总共有 100 行数据:
每个 block 可以存 4 行数据. 存这 100 条数据, 需要 25 个 block. 如果现在我们需要查询其中的一条数据, 最多就需要查询 25 个 block.
什么是索引
我们建一个简单的索引, 有两个字段, 一个 eid, 表示 employee 的 id, 还有一个字段 pointer, 指向数据存储在 disk 上的位置. empolyee 中的每一行, 在 index 上都有一条记录.
那么我们又是怎么存储这个索引的呢? 这里我们假设还是全部存在 disk 上(当然你完全可以选择直接存在内存里). 那么这个索引需要占据多少个 block 呢? eid 大小为 10bytes,pointer 大小为 6bytes, 所以一行索引就有 16 个 bytes 大小. 100 条索引就需要占据 100 * 16 / 512 -> 4 个 block.
那么现在要查询 employee 表中的某一条数据, 最多需要查询多少个 block 呢? 答案是 4+1=5 个. 效率比之前要高了很多.
什么是多级索引
现在假设有 1000 条数据, 这 1000 条数据将占据 250 个 block, 上一小节讲的索引将占据 40 个 block. 现在用索引查询一次, 最多需要 41 次 block access. 现在这个索引已经不能满足我们对性能的追求了, 那么能不能对索引建一个索引呢? 也就是二级索引?
对于二级索引, 不需要记录每条 employee 在 disk 的位置, 只需要记录一级索引所有 block 的位置就行了. 所以, 二级索引需要 40 条记录, 也就是需要占据 2 个 block 的空间. 这种二级索引可以叫做稀疏索引, 他不会包含所有数据行所在的位置.
现在借助二级索引, 查询效率为: 2 + 1 + 1 = 4 次 block access.
随着数据量不断增加, 还可以对二级索引建立三级索引, 对三级索引建立四级索引......
同时, 我们还希望做到一点: 多级索引可以随着数据量的大小变化而自动创建和删除. 这就引出了主角: B 树和 B + 树.
m-way 搜索树
二叉搜索树: 每个节点有一个值, 有两个子节点.
由二叉搜索树扩展, 让每个节点最多可以存 m-1 个索引值, 每个节点可以有 m 个子节点, 就是 m-way 搜索树.
上图所示的就是 3-way 搜索树.
下面的这个 4-way 搜索树, 每个节点最多存了 3 个索引值, 有 4 个指向子节点的 pointer, 同时还有指向数据项所在的位置的指针 Rp.
我们可以用这个 m-way 搜索树作为数据库的索引, 但是, m-way 搜索树存在一些问题:
比如现在有三个数据: 10,20,30, 要用一个 10-way 搜索树来构建. 很有可能, 最终会构建出一个这样的树:
这是最糟糕的一种情况, 最终. 我们需要先把每个节点填满, 然后才能创建下一个子节点. 而 m-way 搜索树本身, 并没有这种强制, 你可以随意插入.
B 树: m-way 搜索树 + 规则
B 树, 实际上可以看作是 m-way 搜索树 + 规则(如何构建这棵树的规则).
规则:
每个节点至少有 [m/2] 个子节点
根节点可以最少有 2 个子节点
所有的叶子节点必须在一个层级
创建过程是由下往上的
B 树中的插入操作
值: 10,20,40,50. 要构建一个 4-way 搜索树. 4-way 搜索树, 意味着一个节点最多可以有 3 个值.
这实际上, 也就构建了一个二级索引. 上面的是第二层索引, 下面的是第一层索引. 每一层构成了一级索引.
继续插入 60 和 70:
接着插入 80, 右下的那个节点已经没有空位置了, 所以需要新建一个节点, 然后把 70 那个值提升到上一层.
插入 30:
插入 35:
等等等等:
每个值旁边, 都有一个指向数据存储位置的指针.
B + 树
在 B + 树中, 不是每个值旁边都有一个指向数据存储位置的指针, 只有叶子节点才有. 非叶子节点的值, 在叶子节点上有他的副本. 如图所示:
这就成为了一个密集索引.
来源: https://juejin.im/post/5c5bdd896fb9a049e93d2f20