B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases

Summary: B^link-hash hybridizes B+-trees with large hash leaves, randomizing monotonically increasing timestamp inserts to alleviate hotspot contention. Median-approximate/lazy splits and adaptive conversion back to tree nodes preserve scans, yielding up to 91.3× higher ingestion throughput. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13178
Venue: VLDB
Year: 2023
Pagerank: 5.4574671e-05
Overall Rank: 8,255 | 43.37%
DOI: 10.14778/3583140.3583143

Incoming Non-self Citations Over Time

Authors

1. Hokeun Cha (University of Wisconsin)
2. Xiangpeng Hao (University of Wisconsin)
3. Tianzheng Wang (Simon Fraser University)
4. Huanchen Zhang (Tsinghua University)
5. Aditya Akella (University of Texas)
6. Xiangyao Yu (University of Wisconsin)

BibTeX Citation

@article{cha_vldb23,
        title = {{B\^{}link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases}},
        author = {Cha, Hokeun and Hao, Xiangpeng and Wang, Tianzheng and Zhang, Huanchen and Akella, Aditya and Yu, Xiangyao},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {6},
        pages = {1235--1248},
        doi = {10.14778/3583140.3583143},
        url = {https://doi.org/10.14778/3583140.3583143},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,440	The Art of Latency Hiding in Modern Database Engines	2024	VLDB	6.7049797e-05
6,742	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	5.7862414e-05
10,149	Bounding the Fragmentation of B-Trees Subject to Batched Insertions	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
491	FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory	2016	SIGMOD	0.00017575163
880	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013432693
882	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.0001342403
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012934147
1,390	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	0.00010942775
1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00010073735
1,710	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.9537123e-05
3,692	Db2 Event Store: A Purpose-Built IoT Database Engine	2020	VLDB	7.199318e-05
5,823	HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication	2020	VLDB	6.0752299e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,082	Pea Hash: A Performant Extendible Adaptive Hashing Index	2023	SIGMOD
2	10,824	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
3	7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB
4	3,747	B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives	2012	VLDB
5	1,492	BF-Tree: Approximate Tree Indexing	2014	VLDB
6	6,549	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD
7	6,429	Just-In-Time Data Structures	2015	CIDR
8	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
9	3,378	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD
10	7,012	Adaptive Hybrid Indexes	2022	SIGMOD