<p>Per the Bloom Filter mentions, Deletable Bloom Filters (DlBF) are in some ways better than basic counting variants.  See <a href="http://arxiv.org/abs/1005.0352" rel="nofollow">http://arxiv.org/abs/1005.0352</a></p>
What are the lesser known but useful data structures?
<p>There are some data structures around that are really useful but are unknown to most programmers. Which ones are they?</p>

<p>Everybody knows about linked lists, binary trees, and hashes, but what about <a href="http://en.wikipedia.org/wiki/Skip_list" rel="nofollow noreferrer">Skip lists</a> and <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">Bloom filters</a> for example. I would like to know more data structures that are not so common, but are worth knowing because they rely on great ideas and enrich a programmer's tool box.</p>

<p>PS: I am also interested in techniques like <a href="http://en.wikipedia.org/wiki/Dancing_Links" rel="nofollow noreferrer">Dancing links</a> which make clever use of properties of a common data structure. </p>

<p><strong>EDIT</strong>:
Please try to <em>include links</em> to pages describing the data structures in more detail. Also, try to add a couple of words on <em>why</em> a data structure is cool (as <a href="https://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-cool-data-structures">Jonas Kölker</a> already pointed out).  Also, try to provide <strong><em>one data-structure per answer</em></strong>. This will allow the better data structures to float to the top based on their votes alone.</p>