A level for a new node is usually chosen as follows. Level 0 with probability 2-1, level 1 - with probability 2-2, level 2 - with probability 2-3, and so on. Maximum possible level for a node can be either some predefined constant (for example, 32 or 64), or based on current number of nodes in the skip list N (for example, log2N). The former strategy produces worse results (unreasonably high level can be chosen accidentally), but does not require maintenance of node count. The latter strategy produces more consistent results, but does require maintenance of node count (which is problematic in a concurrent environment). I've chosen the latter strategy. The straightforward implementation of node count maintenance is to use an atomic fetch-and-add instruction on a centralized counter variable. It destroys scalability, and is not an option. I use the following decentralized algorithm (trading precision for decentralization, thus scalability). Each thread has a private counter, which is incremented after each insert. The counters are periodically aggregated (summed up) to produce a total node count. Period of aggregation is based on an estimation of when total node count will cross next 2^N mark. Here is the algorithm: Move on to Memory Allocation |