Flattened Bucket Storage

简单记录下把一个“桶”展平的思路

对于一个 Key 对应多个元素的时候，比如

bucket 0 -> [10, 20, 30]
bucket 1 -> [5, 8]
bucket 2 -> [100, 200, 300, 400]

一个非常简单的思路是叠个 vector < vector <T> > 来进行实现（或者需要做一次 Key 到 index 的映射等，总之先进行一波化简），这很不错，保证了每一个桶下的元素连续，但是不同的桶之间的元素大概率不是连续的，所以如果在基本是静态数据，读比写多的情况下，可以考虑进一步展平这个桶 ——

可以使用一个连续空间作为数据的存储，然后记录每一个桶之间的 offset，最后就可以快速的进行访问，本质上还是一个下标和存储分离的思路大体上。

std::vector<uint32_t> values;
std::vector<uint64_t> offsets;

我们假设拥有数据

bucket 0 -> [10, 20, 30]
bucket 1 -> [5, 8]
bucket 2 -> [100, 200, 300, 400]

那么展平之后

values: [10, 20, 30, 5, 8, 100, 200, 300, 400]
offsets: [0, 3, 5, 9]

我们就可以简单的通过

auto begin = values.begin() + offsets[i];
auto end   = values.begin() + offsets[i + 1];

来获得这段桶内数据。

不过缺点也非常的明显 —— 动态修改数据困难，比如在中间的桶插入元素，在没有预留空间的情况下就需要修改插入位置之后的所有元素 —— 要 update 桶的 offsetd 以及存储源数据的结构，这个操作非常贵。而开头提到的朴素实现法就非常适合动态修改较多的情况，而且实现简单，同时每个 Bucket 扩容是独立的，比较方便与灵活。