> one possibility was to use something radically different from what we already had, such as including LSM trees or B-trees, commonly used in time series databa

> one possibility was to use something radically different from what we already had, such as including LSM trees or B-trees, commonly used in time series databases. Adding trees would bring the benefit of being able to order data on the fly without inventing a replacement storage model from scratch. > What bothered us most with this approach is that every subsequent read operation would face a performance penalty versus having data stored in arrays. Unless I missed something non-obvious from the article, I'm not convinced B-tree storage inevitably faces a read performance penalty compared with storing data in arrays on storage - because B-trees can be made of arrays. A B-tree can be thought of as a flat set of storage blocks, each of which contains the contents for a range of keys in a representation of your choice, and an index mapping key ranges to storage block locations. Usually the index is the same data structure but smaller, and through this recursive definition you get a tree. This is an unorthodox way of thinking about B-trees but it works and generalises well. That storage block representation can be a sorted array of data if that's what you want. Reading from a B=tree involves locating the storage block using the index, then reading the data you want from the block, in whatever representation is used. Presumably "data stored in arrays" also involves non-contiguous segments in storage at some size of segment, so small lookups involve finding the right segment, perhaps binary search to locate a first key, and then scanning it, and large range scans involve iterating over segments. When the database revolves around fast SIMD array scanning operations, it can do that just as much inside a B-tree block that uses array representations for its contents as it can inside a segment of another array storage structure. Maintaining this structure will slow writes with out of order values, but you have that problem with either data structure.