计算机工程与应用2026，Vol.62Issue(17)：105-117,13.DOI:10.3778/j.issn.1002-8331.2508-0106
双利普希茨网络和区间锁增强的学习型索引
BLELI:Bi-Lipschitz Network and Interval Lock Enhanced Learned Index
摘要
Abstract
Learned indexes accelerate query processing by fitting the mapping between keys and positions,and have become a research hotspot.Mainstream methods employ piece-wise linear functions to improve fitting quality.However,when handling complex data distributions,they require a large number of segments,leading to index size inflation,fre-quent retraining,and degraded query performance.Some studies introduce distribution transformation to mitigate this issue,but existing methods suffer from high training and transformation overheads as well as limited stability.To address these challenges,this paper proposes BLELI(bi-Lipschitz network and interval lock enhanced learned index),which con-structs an efficient index through three key mechanisms:(1)BiLipTransformer,a bi-Lipschitz network-based distribution transformer that is inherently injective,incorporates cross-layer connections to capture features even in shallow architec-tures,and allows smooth control of input-output perturbations to improve transformation stability.(2)Training optimiza-tion leverages integral quadratic constraints and Cayley transform-based parameterization to accelerate convergence.Fur-thermore,it adopts the probability integral transform theorem to target a uniform distribution,reducing conflicts in down-stream fitting.(3)PreciseSeekIndex is an index structure combining model nodes and bucket nodes,which uses the interval lock mechanism to resolve global blocking when local insertions trigger retraining.Experimental results demonstrate that,compared with traditional index structure(B+Tree)and representative learned indexes(RMI,ALEX,LIPP,NFL),BLELI achieves an average 2.05×improvement in throughput and a 53.58%reduction in P99 tail latency across multiple datasets and workloads,effectively overcoming performance and stability bottlenecks under complex data distributions and pro-viding a robust solution for efficient index deployment.关键词
学习型索引/分布转换/双利普希茨网络/概率积分变换/区间锁Key words
learned index/distribution transformation/bi-Lipschitz network/probability integral transform theorem/interval lock分类
信息技术与安全科学引用本文复制引用
余新涛,陈刚..双利普希茨网络和区间锁增强的学习型索引[J].计算机工程与应用,2026,62(17):105-117,13.基金项目
国家自然科学基金(U1936107). （U1936107）
