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

Question

正如我从源代码上看到的

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相比，当按索引进行范围查询时，使用红黑树将失去空间局部性.

Answer 1

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

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

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

• 帕夫洛/地位/989977469863256064
• https://www.slideshare.net/jhugg/everything-we-learned-about-inmemory-data-layout-while-building-voltdb (见幻灯片56-61)

披露:我在VoltDB工作。