外存模型/缓存无关模型下的数据结构

一、Intro

最近在刷MIT 6.851，记录下笔记

1.1. 啥是外存模型

对于现实世界中常见的多级存储，我们只关心最慢的那层（我们把最慢的那层叫disk)，并假设访问其他较快的cache层的时间忽略不计。在外存模型下讨论时间复杂度时，只讨论需要访问disk几次。比如在数组中通过顺序访问来查找一个元素，其时间复杂度是O(N/B)，意思是需要O(N/B)次访问disk。
外存模型下设计出来的最经典的数据结构就是B-tree了。

image.png image.png
image.png

1.2. 啥是cache-oblivious模型

和外存模型一样，但区别是算法不知道M和B各自多大。相比之下，外存模型下的B树还得知道B多大、从而确定一个节点有多少个子节点。
cache-oblivious datastructure是不是叫“不用调参的外存数据结构”比较形象？我自己起的名：）

1.3. 参考资料

Session 7: Memory Hierarchy Models
MIT6_851S12_L7.pdf

课程 20：Cache-Oblivious Algorithms

缓存无关数据结构

二、实现cache-oblivious BBST

2.1. 把static BBST改造成cache-oblivious

假设树完美平衡，可以用vEB序存储，实现cache-oblivious。个人觉得叫分形三角形存储比较形象。

image.png

如图把树分解成多个三角形子树（按树高一半划分），每个子树再分解成多个子树，每个子树再分解……总之就是分形三角形。
总有一层分形的大小能满足：一次外存读取的时候刚好能读出来k个分形三角形外加其他分形三角形的一部分，但是又没法一次读出来更大块的分形。可以证明查询的时间复杂度是O(logbN)：

image.png

2.2. 动态BBST

2.2.1. 核心思想

对于要保留顺序的动态数据结构，挑战在于外存模型改点东西成本较大（比如红黑树旋转一下可能就得几次访外），最好是用那种预留一定空间、新增删除时候结构不会变（很少变）的数据结构，这样访外次数少。比如有序文件就是这样的数据结构。
有序文件插入时要平移元素，也是cache-oblivious操作（课程没细讲，个人理解），但是有序文件不好查找，因为二分查找在外存模型下访问次数太多、性能比较烂。
既然有序文件能cache-oblivious的插入删除，那么怎么让它支持快速查找？直觉上的想法是建索引，有几种索引思路：

• 对于链式结构不好二分的情况，可以建倍增索引，比如跳表
• tree-like index

课程给的解法是用线段树索引，即线段树套有序文件。这也很好理解：毕竟我们已经找到了树的cache-oblivious方案，直接拿来用就行了，省的去研究跳表怎么cache-oblious

image.png

于是我们就有了cache-oblivious的动态BBST：有序文件+cache oblivious BST索引

2.2.2. 优化

可以用indirection进一步优化复杂度，即分块+间接层的思想。
对有序文件进行分块，每块logn大小，基于这些块套cache oblivious线段树索引：

image.png
image.png

这样一来，树索引占的空间就优化掉了log，而底层在每块内查找/修改元素只要顺序访问该块就行。

三、应用：工程实践中的cache-oblivious

mysql Btree应该不是cache oblivious的。
MySQL storage engine TokuDB uses Fractal Tree indexing, a technique based on cache-oblivious algorithms。参考分形树Fractal tree介绍，没看懂

疑问

为什么需要CO数据结构？

如果算法能知道M和B的大小，那么B-tree等外存数据结构就够了吧？
参考Cache-Oblivious Algorithms and Data Structures，有以下原因：

• self-tuning!

Another, more practical consequence is self-tuning. Typical cache-efficient
algorithms require tuning to several cache parameters which are not always
available from the manufacturer and often difficult to extract automatically.
Parameter tuning makes code portability difficult. Perhaps the first and most
obvious motivation for cache-oblivious algorithms is the lack of such tuning:
a single algorithm should work well on all machines without modification. Of
course, the code is still subject to some tuning, e.g., where to trim the base case
of a recursion, but such optimizations should not be direct effects of the cache.

• 多级缓存下每级都最优

One consequence is that, if a cache-oblivious algorithm performs well between
two levels of the memory hierarchy (nominally called cache and disk), then it
must automatically work well between any two adjacent levels of the memory
hierarchy.

A further consequence, if the
number of memory transfers is optimal up to a constant factor between any two
adjacent memory levels, then any weighted combination of these counts (with
weights corresponding to the relative speeds of the memory levels) is also within
a constant factor of optimal. In this way, we can design and analyze algorithms
in a two-level memory model, and obtain results for an arbitrary many-level
memory hierarchy—provided we can make the algorithms cache-oblivious.

就为了不调参都搞出了一类数据结构，那有没有不用调参的线程池？

最近在想这个问题