README
¶
HTree
Package htree implements the in-memory hash tree.
https://pkg.go.dev/github.com/hit9/htree
Example
package main
import (
"fmt"
"github.com/hit9/htree"
)
// Item implements htree.Item.
type Item struct {
key uint32
value string
}
// Key returns the item key.
func (item Item) Key() uint32 {
return item.key
}
func main() {
t := htree.New()
// Add an item.
item := t.Put(Item{123, "data1"})
// Get an item.
item = t.Get(Item{key: 123})
fmt.Println(item)
}
License
BSD.
Documentation
¶
Overview ¶
Package htree implements the in-memory hash tree.
Abstract ¶
Hash-Tree is a key-value multi-tree with fast indexing performance and high space utilization.
Take 10 consecutive prime numbers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
And they can distinguish all uint32 numbers:
2*3*5*7*11*13*17*19*23*29 > ^uint32(0)
Key insertion steps:
- Suppose depth is d, its prime p = Primes[d]
- Get the remainder of key divided by p, r = key % p
- If r is already taken by another node, go to the next depth.
- Otherwise create a new child node and bind r to it.
Example htree:
ROOT
| %2
+-- 0: A(12) 12%2=0: A
| | %3
| +-- 0: C(6) 6%2=0 && 6%3=0: C
| |-- 1: D(4) 4%2=0 && 4%3=1: D
| +-- 2: E(8) 8%2=0 && 8%3=2: E
+-- 1: B(3) 3%2=1: B
| %3
+-- 0: F(9) 9%2=1 && 9%3=0: F
|-- 1: G(7) 7%2=1 && 7%3=1: G
+-- 2: H(11) 11%2=1 && 11%3=2: H
Complexity ¶
Child nodes are stored in an array orderly, and checked by binary-search but not indexed by remainders, array indexing will result redundancy entries, this is for less memory usage, with a bit performance loss. A node is created only when a new key is inserted. So the worst time complexity is O(Sum(lg2~lg29)), is constant level, and the entries utilization is 100%.
Compare To Map ¶
Although hashtable is very fast with O(1) time complexity, but there is always about ~25% table entries are unused, because the hash-table load factor is usually .75. And this htree is suitable for memory-bounded cases.
HTree is better for local locks if you want a safe container.
Map may need to rehash and resize on insertions.
Goroutine Safety ¶
No. Lock granularity depends on the use case.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HTree ¶
type HTree struct {
// contains filtered or unexported fields
}
HTree is the hash-tree.
func (*HTree) NewIterator ¶
NewIterator returns a new iterator on this htree.
type Item ¶
type Item interface {
// Key returns an uint32 number to distinguish node with another.
Key() uint32
}
Item is a single object in the tree.
Source Files