基于范围简图的有序链表快速查询方法和装置

摘要

本发明涉及一种基于范围简图的有序链表快速查询方法和装置。将有序链表切分为多个首尾相连的链表段，通过使用两个紧凑数据结构Buckets Array(桶数组)和Range Sketch(范围简图)，可以快速定位待查询的键值所对应的结点必然存在于一个常数长度的链表段上，保证了查询结果可以在访问常数个结点之后给出，提升了有序链表查询的速度。通过调整RangeSketch中单元数组的长度和使用的哈希函数的个数，可以灵活地处理查询速度和内存占用之间的平衡，兼顾内存使用的高效率和键值查询的高性能。