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 .
Let’s start.
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
Sample :
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 .
