提出一种常数时间搜索结构，突破传统树的性能瓶颈。
Linked Array Tree: A Constant-Time Search Structure for Big Data
- 采用稀疏分层布局，直接访问路径无需重构或数据移动。
- 搜索、插入、删除操作均实现常数时间复杂度。
- 适合大规模数据场景，内存开销低，潜在支持并发环境。
随着数据量持续快速增长，传统搜索算法如红黑树和B+树在大数据场景下面临性能挑战，尤其在密集存储访问时。本文提出一种新型数据结构——链接数组树（Linked Array Tree, LAT），旨在实现搜索、插入和删除操作的常数时间复杂度。LAT采用稀疏且不移动的分层布局，提供直接访问路径，避免了重新平衡和数据移动。其低内存开销及对指针结构的规避，使其适用于大规模和高负载场景。尽管未在并行或并发环境下测试，但其静态布局和非干扰性操作表明在这些环境中具有潜在优势。论文首先介绍LAT的结构与算法，随后详细分析其搜索、插入和删除操作的时间复杂度。最后，在数据密集型和稀疏使用场景中进行实验，评估LAT的实际性能。
原文摘要 · Abstract (English)
As data volumes continue to grow rapidly, traditional search algorithms, like the red-black tree and B+ Tree, face increasing challenges in performance, especially in big data scenarios with intensive storage access. This paper presents the Linked Array Tree (LAT), a novel data structure designed to achieve constant-time complexity for search, insertion, and deletion operations. LAT leverages a sparse, non-moving hierarchical layout that enables direct access paths without requiring rebalancing or data movement. Its low memory overhead and avoidance of pointer-heavy structures make it well-suited for large-scale and intensive workloads. While not specifically tested under parallel or concurrent conditions, the structure's static layout and non-interfering operations suggest potential advantages in such environments. This paper first introduces the structure and algorithms of LAT, followed by a detailed analysis of its time complexity in search, insertion, and deletion operations. Finally, it presents experimental results across both data-intensive and sparse usage scenarios to evaluate LAT's practical performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。