A better concurrency friendy data structure than B Tree.
In previous article — B Tree Step by Step . you can see it is a high performance data structure for searching .however:
- It is complex .
- when dealing with rebalance. the cost is high.
- what if under multi-processing (threading) environment ? it is even more compex .
In this article I only need your 5 mins time to walk through another Data structure which is simple (compare to B tree) yet powerful ,kind of a “multi-level link list” — Skiplist .
A Skip Lists Sample
Attributes of skip list :
- Keys in sorted order.
- O(log n) levels
- Each higher level contains 1/2 the elements of the level below
To build a perfect linked list. can start from bottom (which is a normal link list). then every upper layer link half of the elements . (as showing above)
Now lets see some operation .
It’s simple. max visit log(N) levels then find the value : when value < current, go next level; otherwise check next node .
Step1: Locate the index to insert .
Step2: Build the link for each level. (Adjustment)
Depends on the position to insert, Need adjust(add/remove) max log(N) node links .
After insert (and rebuild links):