Segment tree for bytes in Go

bsegtree

Segment tree for bytes in Go

Based on Thomas Oberndörfer's int range segment tree with fixing/optimization/modification for bytes ranges.

  1. For build once, query many models
  2. Not design for big data set (better for <= 1024 intervals, otherwise the cost will be quite high when query a big range. Bench it before using. For small count intervals. e.g., 1024, the point query will be ~100ns if only one interval id will be returned)
  3. Not design for interval has long bytes as range
  4. Using pseudo-codes in Computational Geometry: Algorithms and Applications, INSERTSEGMENTTREE & codes in another segment tree implementation to fix wrong query result for some corner cases. See func TestMissingResult(t *testing.T) in bstree_test.go

Details of Implementation

  1. Using uint64 as abbreviated key for speeding up query & push, which means long keys with long common prefix won't work with this lib.
  2. Build is slow, offline building is preferred in production environment.
  3. Invoker has responsibility to map the id and target, query will only return the id. ID is started from 0, each push will plus 1.

Performance

Tested on my WSL env:

➜  bsegtree git:(main) ✗ go test -v -run=^a -bench=.
goos: linux
goarch: amd64
pkg: github.com/templexxx/bsegtree
cpu: Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz
BenchmarkBuildSmallTree
BenchmarkBuildSmallTree-6                 269674              3762 ns/op
BenchmarkBuildMidTree
BenchmarkBuildMidTree-6                     1405            821122 ns/op
BenchmarkQueryFullTree
BenchmarkQueryFullTree-6                  348902              3253 ns/op
BenchmarkQueryFullTreeSerial
BenchmarkQueryFullTreeSerial-6            365487              3239 ns/op
BenchmarkQueryPartTree
BenchmarkQueryPartTree/1_result
BenchmarkQueryPartTree/1_result-6       13721766                87.73 ns/op
BenchmarkQueryPartTree/4_result
BenchmarkQueryPartTree/4_result-6        5614016               210.8 ns/op
BenchmarkQueryPartTree/16_result
BenchmarkQueryPartTree/16_result-6       2201541               543.4 ns/op
BenchmarkQueryPartTree/64_result
BenchmarkQueryPartTree/64_result-6        942684              1248 ns/op
BenchmarkQueryPartTree/256_result
BenchmarkQueryPartTree/256_result-6       644641              1668 ns/op
BenchmarkQueryPartTree/1024_result
BenchmarkQueryPartTree/1024_result-6      309175              3247 ns/op
BenchmarkQueryPartTreeSerial
BenchmarkQueryPartTreeSerial/1_result
BenchmarkQueryPartTreeSerial/1_result-6                  1426617               838.4 ns/op
BenchmarkQueryPartTreeSerial/4_result
BenchmarkQueryPartTreeSerial/4_result-6                  1434604               836.1 ns/op
BenchmarkQueryPartTreeSerial/16_result
BenchmarkQueryPartTreeSerial/16_result-6                 1389748               863.0 ns/op
BenchmarkQueryPartTreeSerial/64_result
BenchmarkQueryPartTreeSerial/64_result-6                 1208978               986.5 ns/op
BenchmarkQueryPartTreeSerial/256_result
BenchmarkQueryPartTreeSerial/256_result-6                 754640              1434 ns/op
BenchmarkQueryPartTreeSerial/1024_result
BenchmarkQueryPartTreeSerial/1024_result-6                317222              3175 ns/op
BenchmarkQueryPoint
BenchmarkQueryPoint-6                                   11519022                99.12 ns/op
BenchmarkQueryPointSerial
BenchmarkQueryPointSerial-6                              1428042               837.5 ns/op
BenchmarkQueryPointSerialCapacity
BenchmarkQueryPointSerialCapacity/4
BenchmarkQueryPointSerialCapacity/4-6                   44112619                26.11 ns/op
BenchmarkQueryPointSerialCapacity/16
BenchmarkQueryPointSerialCapacity/16-6                  32856278                34.68 ns/op
BenchmarkQueryPointSerialCapacity/64
BenchmarkQueryPointSerialCapacity/64-6                  14142586                83.04 ns/op
BenchmarkQueryPointSerialCapacity/256
BenchmarkQueryPointSerialCapacity/256-6                  5421559               221.6 ns/op
BenchmarkQueryPointSerialCapacity/1024
BenchmarkQueryPointSerialCapacity/1024-6                 1551112               772.8 ns/op
BenchmarkQueryPointCapacity
BenchmarkQueryPointCapacity/4
BenchmarkQueryPointCapacity/4-6                         38701812                30.69 ns/op
BenchmarkQueryPointCapacity/16
BenchmarkQueryPointCapacity/16-6                        27751310                42.75 ns/op
BenchmarkQueryPointCapacity/64
BenchmarkQueryPointCapacity/64-6                        14492997                83.11 ns/op
BenchmarkQueryPointCapacity/256
BenchmarkQueryPointCapacity/256-6                       12500755                94.16 ns/op
BenchmarkQueryPointCapacity/1024
BenchmarkQueryPointCapacity/1024-6                      11824395               102.3 ns/op
PASS
ok      github.com/templexxx/bsegtree   41.750s

Fast enough for not big intervals (<= 1024) query, have been met my needs.

Owner
Temple3x
Storage Engineer
Temple3x
Similar Resources

B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (500LOC) and highly do

Dec 31, 2022

Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

Mar 7, 2022

Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Oct 6, 2021

Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

May 17, 2022

Golang channel example with equivalent binary tree

Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

Oct 9, 2021

A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

Nov 1, 2021

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

Nov 24, 2021

publish a tree-like data structure from a backend to a front-end

tree-publish publish a tree-like data structure from a backend to a front-end. It needs to be a tree in order to publish the data as JSON document. If

Dec 20, 2021

Mmpxmas-go - ModMyPi Programmable Christmas Tree examples written in Go with go-rpio

ModMyPi Programmable Christmas Tree examples in Go This small program contains examples similar to the examples provided by ModMyPi for interacting wi

Jan 4, 2022
take bytes out of things easily ✨🍪
take bytes out of things easily ✨🍪

crunch a library for easily manipulating bits and bytes in golang features | installation | benchmarks | examples features feature-rich: supports read

Nov 20, 2022
A tree like tool help you to explore data structures in your redis server
 A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

Mar 17, 2022
A Merkle Tree implementation written in Go.
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Jan 5, 2023
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Nov 3, 2022
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

Mar 23, 2022
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Apr 25, 2022
an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Jan 3, 2023
An R-tree implementation for Go
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Dec 29, 2022
Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Dec 25, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

Dec 29, 2022