...

查询：直接查询跳表的引用

内存占用

单序列一百万个点

Array: 4MB4 MB

SkipList：52 MB （Integer：16 MB, SkipListNode：36 MB）SkipList：52MB （Integer：16MB, SkipListNode：36MB）

十万序列每序列十个点

SkipList：59.6 MB (SkipList: 58MB58 MB, ref: 1.6MB6 MB)

Array: 5.6MB 6 MB (data: 4MB4 MB, ref: 1.6MB6 MB)

单线程写入+查询

单序列一千万个点

写入

Array：360msArray：360 ms

SkipList：8921msSkipList：8921 ms

查询

Array：449msArray：449 ms

SkipList：76msSkipList：76 ms

一千序列每序列一万个点

写入

Array：428msArray：428 ms

SkipList：9138msSkipList：9138 ms

查询

Array：393msArray：393 ms

SkipList：92msSkipList：92 ms

十万序列每序列一百个点

写入

Array：429msArray：429 ms

SkipList：10129msSkipList：10129 ms

查询

Array：172msArray：172 ms

SkipList：119msSkipList：119 ms

并发写入+查询

测试方法

单线程写入，同时匹配n个线程查询，测试在有查询的负载下，写入线程最终完成写入的总时间

n: 查询线程数

单序列一千万个点

n = 1

Array：528msArray：528 ms

SkipList: 12413ms12413 ms

n = 3

Array：702msArray：702 ms

SkipList: 14202ms14202 ms

n = 5

Array：1131msArray：1131 ms

SkipList: 16304ms16304 ms

十万序列每序列一百个点

n = 1

Array：1056msArray：1056 ms

SkipList：10243msSkipList：10243 ms

n = 3

Array：1539msArray：1539 ms

SkipList：11620msSkipList：11620 ms

n = 5

Array：2064msArray：2064 ms

SkipList：13714msSkipList：13714 ms

结论

（1）内存占用：skiplist 的内存占用为 array 的10倍左右

...