为什么 VoltDB 选择红黑树作为索引结构？

Why VoltDB choose Red-Black Tree as index structure?

从 source code 可以看出：

enum TableIndexType {
    BALANCED_TREE_INDEX     = 1,
    HASH_TABLE_INDEX        = 2,
    BTREE_INDEX             = 3, // unused
    COVERING_CELL_INDEX     = 4
};

VoltDB主要使用BALANCED_TREE_INDEX作为索引结构，内部使用CompactingMap（一种红黑树实现）。

相对于b+tree，使用索引进行范围查询时，使用红黑树会失去空间局部性。

VoltDB 选择红黑树实现的主要原因是为了避免内存碎片并保持平衡。性能需要在数据的整个生命周期内保持一致，而不是使用不太灵活的结构，这种结构在某些情况下会更快，但会随着时间的推移降低性能或变得不那么理想。

存储在 VoltDB 表中的记录可能包含各种数据类型和列数，并且它们可能在内存中保留不同的时间。索引通常包含多个列。对于 VARCHAR 列，小于 64 字节的值存储在索引中，但对于更大的值，索引使用指向池内存中值的一个副本的指针。

您可以在这里阅读更多关于推理的内容：

披露：我在 VoltDB 工作。