思考 1：固态硬盘的普及，是否影响到了存储引擎的设计？

Reference: Let’s Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems

在设计数据库系统的时候，通常要在“易失性存储”和“非易失性存储”之间做权衡。为了在掉电之后仍然能够保存数据，人们将内存数据写入持久化存储中，然后用 Write-ahead log 来保持内存和磁盘刷写一致。在早期，持久化存储通常是一些 HDD 设备，相比 DRAM，它们读写缓慢，且数据传输粒度通常比较大。

为了平衡内存和磁盘的读写速度差异，人们做出了很多努力。比如在磁盘上维护有序结构时采用 B-tree （将树的高度降下来，减少磁盘 I/O 次数。3~4 层的 B-tree 已经可以适合大多数数据库，degree 为 500 的 4 KB 页的四级树可以存储高达 256 TB）。比如在写磁盘时，为了减少直接的原地更新（In-place Updates）带来的效率问题，采用一些“懒”方案（例如 Copy-on-Write Updates，Log-structured Updates）。另外，在 SSD 上，固件内部使用 Log-structured 算法将“随机写入”转换为底层存储芯片上的“顺序写入”，也是为了加快写磁盘的速度。

近年来，固态硬盘的普及，一定程度上减少了内存与磁盘之间的读写速度差异，它是否会对原有的存储引擎的设计产生影响？

以及，未来如果非易失性存储普及，又会对存储引擎的设计产生哪些影响？

思考 2：B+ tree 的选型原因

Reference: Skip Lists: A Probabilistic Alternative to Balanced Trees

完整说一下吧，无论 B/B+，RB，AVL，还是 skiplist，在最开始都实际上面临同一个问题，在数据有序的情况下，都会成为一个链表。最后导致查询复杂度 O(N)， B/B+/RB/AVL 的采用的策略是 self adjust ，就是所谓的 rebalance。跳表的策略是做 randomize，他假定了一个概率 P，有一个“退化”描述，即，当 P =1/2 时，有百分之50%的数据在第一层，百分之25的数据在第二层，百分之12.5的数据在第三层 etc. 通过这样让数据分层明显，避免全局退化。所以在这种情况下 skiplist 在期望复杂度上做到了查询 O(logn)（实际上这也是一个统计上的期望计算）。skiplist 的优势也很明显，实现简单，性能不错，但是缺陷也很明显，在内存的情况下，由于其是个 randomize 的数据结构，导致其 CPU cache的利用率并不是很明显，所以可能要考虑这块的场合还是需要去用 RB 这种数据结构。在磁盘 I/O 的情况下，由于其 randomize 的特性，导致你没法去做 Sequential reading ，而 randomize reading 对于磁盘来说一直是个大问题。在这个问题上 RB 这种数据结构实际上面临的问题也是一样的，所以 B/B+ 树用适当的数据聚合的方式，将树的高度降下来，方面我们做 page read，避免 randomize reading

稳定这话实际上也没说错，，因为 skiplist 毕竟是个 randomize 的数据结构，他复杂度取还是概率上的描述23333（并不保障严格的平衡性 lol