个人博客查询类型
大多数 SQL 查询可以分为 3 种类型：
- 扫描整个数据集。（不使用索引）。
- 点查询：通过特定键查询索引
- 范围查询：按范围查询索引。（索引已排序）
数据库索引主要是范围查询和点查询，很容易看出范围查询只是点查询的超集。 如果我们提取数据库索引的功能，那么制作一个键值存储就很简单了。 但重点是数据库系统可以构建在KV存储之上。
在尝试关系数据库之前，这里将构建一个KV存储，先谈谈该怎么选择。
哈希表
设计通用KV存储时，哈希表是第一个被排除在外的。主要原因是排序—许多实际应用程序确实需要排序。
然而，在专门的应用程序中使用哈希表是可以的。使用哈希表的另一个令人头疼的问题是调整大小操作。 单纯调整大小的时间复杂度为 O(n)，并会导致磁盘空间和 IO 突然增加。 虽然可以逐步调整哈希表的大小，但这会增加复杂性。
B树
B 树是平衡的 n 叉树，与平衡二叉树相当。每个节点存储可变数量的键（和分支）。
使用较短的树减少随机访问：
磁盘每秒只能执行有限数量的 IO (IOPS)，这是树查找的限制因素。树的每一层都是查找中的磁盘读取，对于相同数量的键，n 叉树比二叉树短（ lognN 与 log2N ），因此n叉 树用于减少每次查找的磁盘读取次数。
如何选择 n ？有一个权衡：
- 较大的 n 意味着每次查找的磁盘读取次数更少（更好的延迟和吞吐量）。
- 较大的 n 意味着较大的节点，更新速度较慢（稍后讨论）。
IO以页为单位：
虽然可以从文件的任意偏移处读取任意数量的字节，但磁盘却不能以这种方式工作。磁盘IO的基本单位不是字节，而是扇区，扇区是老的HDD上的512字节连续块。
磁盘扇区不是应用程序关心的问题，因为常规文件 IO 不直接与磁盘交互。操作系统在页面缓存中缓存/缓冲磁盘读取/写入，页面缓存由称为页面的 4K 字节内存块组成。
不管怎样，都有一个最小的IO单位。 DB 还可以定义自己的 IO 单元（也称为页），该单元可以大于操作系统页。
最小IO单元意味着树节点应该以该单元的倍数分配；一半使用的单元就是一半浪费的 IO。反对小 n 的另一个原因！
B树变体 — B+树
在数据库上下文中，B 树一般指B 树的变体，称为 B+树。在B+树中，内部节点不存储值，值仅存在于叶节点中。这会导致树更短，因为内部节点有更多的空间用于分支。
B+tree 作为内存中的数据结构也是有意义的，因为 RAM 和 CPU 缓存之间的最小 IO 单元是 64 字节（缓存行）。性能优势不如磁盘上那么大，因为 64 字节无法容纳太多内容。
备注：
哈希表调整大小的复杂度
取决于具体的实现方式。一般来说，调整哈希表大小的操作需要重新计算哈希值并将旧的元素重新插入到新的哈希表中。因此，调整大小的复杂度取决于哈希表中元素的数量和新哈希表的大小。一般来说，调整大小的复杂度为 O(n)，其中 n 是哈希表中元素的数量。但是，一些实现方式可以在调整大小时优化，例如使用增量式重新哈希或使用双倍扩容策略，这些方式可以将调整大小的复杂度降低到 O(1) 或 O(log n)。
