README.md
1treap
2=====
3
4[](https://travis-ci.org/btcsuite/btcd)
5[](http://copyfree.org)
6[](http://godoc.org/github.com/btcsuite/btcd/database/internal/treap)
7
8Package treap implements a treap data structure that is used to hold ordered
9key/value pairs using a combination of binary search tree and heap semantics.
10It is a self-organizing and randomized data structure that doesn't require
11complex operations to to maintain balance. Search, insert, and delete
12operations are all O(log n). Both mutable and immutable variants are provided.
13
14The mutable variant is typically faster since it is able to simply update the
15treap when modifications are made. However, a mutable treap is not safe for
16concurrent access without careful use of locking by the caller and care must be
17taken when iterating since it can change out from under the iterator.
18
19The immutable variant works by creating a new version of the treap for all
20mutations by replacing modified nodes with new nodes that have updated values
21while sharing all unmodified nodes with the previous version. This is extremely
22useful in concurrent applications since the caller only has to atomically
23replace the treap pointer with the newly returned version after performing any
24mutations. All readers can simply use their existing pointer as a snapshot
25since the treap it points to is immutable. This effectively provides O(1)
26snapshot capability with efficient memory usage characteristics since the old
27nodes only remain allocated until there are no longer any references to them.
28
29Package treap is licensed under the copyfree ISC license.
30
31## Usage
32
33This package is only used internally in the database code and as such is not
34available for use outside of it.
35
36## License
37
38Package treap is licensed under the [copyfree](http://copyfree.org) ISC
39License.
40
){kind=link}
){kind=link}
){kind=link}