In most cases queries must be answered on-line, so randomly permuting the input is impractical, therefore balanced trees have to be explicitly rebalanced. One of the inherent problems of the B-Tree is the time it takes to rebalance the tree. This rebalancing has a such a noticeable effect that many B-tree implementations go to great lengths to avoid, or at least to delay rebalancing. The additional software needed to achieve this delayed rebalancing only adds to the complexity of the B-Tree algorithm. Balanced trees algorithms re-arrange the tree as operations are performed to maintain certain balance conditions and assure good performance.
Skip lists are a probabilistic alternative to balanced trees.
Skip lists are balanced by consulting a random number generator. Skip lists have balance properties similar to that of search trees built by random insertions, yet do not require insertions to be random. Balancing a data structure probabilistically is easier than explicitly maintaining the balance. For many applications, skip lists are a more natural representation than trees, also leading to simpler algorithms. The simplicity of skip list algorithms makes them easier to implement and provides significant constant factor speed improvements over balanced tree and self-adjusting tree algorithms.