tidwall/celltree

Stars
201
Rank 194,491 (Top 4 %)
Language
Go
License
MIT License
Created over 6 years ago
Updated almost 4 years ago

tidwall/celltree

tidwall

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

A fast in-memory prefix tree that uses uint64 for keys and allows for duplicate entries.

`celltree`

A fast in-memory prefix tree that uses uint64 for keys, interface{} for data, and allows for duplicate entries.

Getting Started

Installing

To start using celltree, install Go and run go get:

$ go get -u github.com/tidwall/celltree

Example

var tr celltree.Tree

tr.Insert(10, nil)
tr.Insert(5, nil)
tr.Insert(31, nil)
tr.Insert(16, nil)
tr.Insert(9, nil)

tr.Scan(func(cell uint64, data interface{}) bool {
    println(cell)
    return true
})

Outputs:

Performance

Single threaded performance comparing this package to google/btree.

$ go test

-- celltree --
insert    1,048,576 ops in  318ms  3,296,579/sec
scan            100 ops in  824ms        121/sec
range     1,048,576 ops in  144ms  7,245,252/sec
remove    1,048,576 ops in  244ms  4,281,322/sec
memory    40,567,280 bytes 38/entry

-- btree --
insert    1,048,576 ops in 1003ms  1,044,876/sec
scan            100 ops in 1195ms         83/sec
range     1,048,576 ops in  443ms  2,364,467/sec
remove    1,048,576 ops in 1198ms    874,723/sec
memory    49,034,992 bytes 46/entry

These benchmarks were run on a MacBook Pro 15" 2.8 GHz Intel Core i7 using Go 1.10

Contact

Josh Baker @tidwall

License

celltree source code is available under the MIT License.

gjson

Get JSON values quickly - JSON parser for Go

tile38

Real-time Geospatial and Geofencing

evio

Fast event-loop networking for Go

buntdb

BuntDB is an embeddable, in-memory key/value database for Go with custom indexing and geospatial support

redcon

Redis compatible server framework for Go

sjson

Set JSON values very quickly in Go

SwiftWebSocket

Fast Websockets in Swift for iOS and OSX

summitdb

In-memory NoSQL database with ACID transactions, Raft consensus, and Redis API

jj

JSON Stream Editor (command line utility)

btree

B-tree implementation for Go

hashmap.c

Hash map implementation in C.

uhaha

High Availability Raft Framework for Go

pinhole

3D Wireframe Drawing Library for Go

finn

Fast Raft framework using the Redis protocol for Go

wal

Write ahead log for Go.

tg

Geometry library for C - Fast point-in-polygon

Safe

Modern Concurrency and Synchronization for Swift.

pretty

Efficient JSON beautifier and compactor for Go

chanx

A simple interface wrapper around a Go channel.

rtree

An R-tree implementation for Go

btree.c

B-tree implementation in C

GoSwift

Go Goodies for Swift. Including goroutines, channels, defer, and panic.

shardmap

A simple and efficient thread-safe sharded hashmap for Go

hashmap

A simple and efficient hashmap package for Go. Open addressing, robin hood hashing, and xxh3 algorithm. Supports generics.

gjson.rs

Get JSON values quickly - JSON parser for Rust

cities

10,000 Cities with Latitude, Longitude, and Elevation in Go

tinylru

A fast little LRU cache for Go

Avios

Realtime H264 decoding library for iOS.

jd

Interactive JSON Editor

pinhole-js

3D Wireframe Drawing Library for HTML Canvas

mmap

Load file-backed memory

geojson

GeoJSON for Go. Used by Tile38

doppio

Doppio is a fast LRU cache on top of Ristretto, Redcon, and Evio. Support for the Redis protocol.

rtree.rs

A fast R-tree for Rust

match

Simple string pattern matcher for Go

rtree.c

An R-tree implementation in C

tinybtree

Just an itsy bitsy b-tree in Go

jsonc

Parse json with comments and trailing commas.

rhh

A simple and efficient hashmap package for Go. Uses open addressing, Robin Hood hashing, and xxhash algorithm.

kvnode

key value server. redis api, leveldb storage, raft support

raft-fastlog

Raft in-memory backend implementation with persistence

resp

Reader, Writer, and Server implementation for the Redis RESP Protocol.

modern-server

Basic web server framework with HTTP/2 and Let's Encrypt.

limiter

A goroutine limiter for Go

redraft

Redis + Raft server implementation

redcon.rs

Redis compatible server framework for Rust

rocksdb-server

Fast Redis clone written in C using RocksDB as a backend.

lotsa

Simple Go library for executing lots of operations spread over any number of threads

box

Efficiently box values in Go. Optimized for primitives, strings, and byte slices.

evio-lite

Fast event-loop networking for Go (the lite version)

transform

Using io.Reader for data transformation in Go

uspto-trademark

How to file a USPTO trademark without an attorney for $225

pjson

A JSON stream parser for Go

geodesic

Go package for performing accurate measurements of Earth. Includes the geodesic routines from GeographicLib.

expr

Expression evaluator for Go

json.c

Fast JSON parser for C

spinlock

A spinlock implementation for Go.

raft-wal

Write ahead Raft log for Go

rtred

RTree implementation for Go

bfile

A buffer pool file I/O library for Go

mvt

Draw Mapbox Vector Tiles (MVT) in Go

redcon.c

Redis compatible server framework for C

cache-server

A minimal key/value server written in Rust with Redis API support.

spanmap

A fast collection type that uses uint64 for keys.

go-node

Run Javascript in Go using Node.js

ticketd

A distributed service for monotonically increasing tickets.

hexd

Please love the nicely formatted hex.

DeflateSwift

Deflate Compression for Swift

proximity-chat

Chat app for real-time chats with people within 500 meters.

lru

A simple and efficient LRU cache package for Go

sider

A Redis clone written in Go

xv

An expression evaluator for C

geometry

Efficient 2D geometry library for Go.

pkg.sh

A generalized package manager for whatever code.

rfront

An HTTP protocol frontend for Redis-compatible services.

redis-gis

Redis fork with Geospatial support based on Tile38 commands

RetroSwiper

Load classic games from magnetic swipe cards

uhasql

A high availability Sqlite service

redbench

Benchmarking for custom Redis commands and modules

sds

simple data streams for go

spmap

A hashmap for Go that uses crypto random seeds, hash hints, open addressing, and robin hood hashing.

IoniconsSwift

Ionicons for Swift and iOS

raft-leveldb

Raft backend using LevelDB

evio.c

A framework for building event based networking applications.

tinyqueue

Binary heap priority queues in Go

kvbench

Server for benchmarking pure Go key/value databases

gjson-play

A playground for GJSON. Runs in the browser.

randjson

Make random JSON in Go

redlog

Redis style logger for Go

SnapHTTP

An incredibly simple HTTP client library for Swift.

qtree

jeez it's just a quadtree chill out

rtime

Retrieve the current time from remote servers

fast-spatial-joins

Go vs GPU: Fast Spatial Joins

assert

An assert function for Go that works like the one in C.

pair

create low memory key/value objects in Go

match.c

Simple string pattern matcher for C

secret

A simple utility for encrypting and decrypting data in Go (AES-256-CFB)

pony

🌈 🐴 Turn your terminal text into an absolutely beautiful display of dazzling colors....

btree-benchmark

Benchmark utility for the tidwall/btree Go package

lru-server

A convenient LRU cache server that supports REST API and Let's Encrypt.