3 ms·
Might anyone familiar with both data structures be able to briefly explain how this actually differs from a B-tree?
by ddebernardy 10y ago
Might anyone familiar with both data structures be able to briefly explain how this actually differs from a B-tree?
- aidenn0 10y agoThere are a lot of differences; here's a couple: A skip list node contains one key and has a random fanout; a B-tree node contains 1-N keys and has fanout equal to <number of keys> - 1. A B-tree is guaranteed amortized log(N) lookup/insert/delete time, a skip-list has a high probability of a log(N) lookup/insert/delete time, but does not guarantee it. The advantage of skip lists over b-trees is that they can have a smaller constant-factor, and are more cache friendly under many workloads.