Proceedings of the VLDB Endowment · 2023 · 14 citations · 12 references
ComputingComputer EngineeringComputer ScienceData StructuresDatabasesInternet Of ThingsHash FunctionsHash TablesHigh-throughput ComputingMemory Hierarchy OptimizationQuery ProcessingB+ TreesHashingIndex DesignIndexesInsertionsScalabilityScalability BottlenecksThroughput
High-speed data ingestion is critical in time-series workloads that are driven by the growth of Internet of Things (IoT) applications. We observe that traditional tree-based indexes encounter severe scalability bottlenecks for time-series workloads that insert monotonically increasing timestamp keys into an index; all insertions go to a small memory region that sees extremely high contention. In this work, we present a new index design, B link -hash, that enhances a tree-based index with hash leaf nodes to mitigate the contention of monotonic insertions --- insertions go to random locations within a hash node (which is much larger than a B+-tree node) to reduce conflicts. We develop further optimizations (median approximation and lazy split) to accelerate hash node splits. We also develop structure adaptation optimizations to dynamically convert a hash node to B+-tree nodes for good scan performance. Our evaluation shows that B link -hash achieves up to 91.3× higher throughput than conventional indexes in a time-series workload that monotonically inserts timestamps into an index, while showing comparable scan performance to a well-optimized B+-tree.
12
Rasmus Pagh, Flemming Friche Rodler · Journal of Algorithms · 2004 · 1.1K citations
M2M: From mobile to embedded internet
Geng Wu, Shilpa Talwar, Kerstin Johnsson et al. · IEEE Communications Magazine · 2011 · 749 citations
Concurrency of operations on B-trees
Raymond Bayer, Mario Schkolnick · Acta Informatica · 1977 · 405 citations