  Waves of misery is a phenomenon where spikes of many node splits occur over
short periods of time in tree indexes. Waves of misery negatively affect the
performance of tree indexes in insertion-heavy workloads.Waves of misery have
been first observed in the context of the B-tree, where these waves cause
unpredictable index performance. In particular, the performance of search and
index-update operations deteriorate when a wave of misery takes place, but is
more predictable between the waves. This paper investigates the presence or
lack of waves of misery in several R-tree variants, and studies the extent of
which these waves impact the performance of each variant. Interestingly,
although having poorer query performance, the Linear and Quadratic R-trees are
found to be more resilient to waves of misery than both the Hilbert and
R*-trees. This paper presents several techniques to reduce the impact in
performance of the waves of misery for the Hilbert and R*-trees. One way to
eliminate waves of misery is to force node splits to take place at regular
times before nodes become full to achieve deterministic performance. The other
way is that upon splitting a node, do not split it evenly but rather at
different node utilization factors. This allows leaf nodes not to fill at the
same pace. We study the impact of two new techniques to mitigate waves of
misery after the tree index has been constructed, namely Regular Elective
Splits (RES, for short) and Unequal Random Splits (URS, for short). Our
experimental investigation highlights the trade-offs in performance of the
introduced techniques and the pros and cons of each technique.
