A data structure for storing points.

Overview

ptree

GoDoc

This package provides an in-memory data structure for storing points.

Under the hood it stores points in a tree structure where nodes are spatially split evenly over a 16x16 grid and leaf nodes hold up to 256 points each.

Cities

It has an api that works a lot like the tidwall/rtree library, but ptree is limited to only storing point while rtree can store points and rectangles. It's also structurally closer to an quadtree than an rtree.

Here's what the R-tree looks like in comparison

Cities

Performance

The following benchmark inserts 1,000,000 random points, searches for each point, and then deletes each point.

P-tree

insert:  1,000,000 ops in 225ms, 4,449,671/sec, 224 ns/op
search:  1,000,000 ops in 287ms, 3,485,059/sec, 286 ns/op
delete:  1,000,000 ops in 220ms, 4,545,320/sec, 220 ns/op

R-tree

insert:  1,000,000 ops in 645ms, 1,551,015/sec, 644 ns/op
search:  1,000,000 ops in 612ms, 1,634,557/sec, 611 ns/op
delete:  1,000,000 ops in 974ms, 1,026,674/sec, 974 ns/op

MacBook Pro 15" 2.8 GHz Intel Core i7

License

ptree source code is available under the MIT License.

You might also like...
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Generates data structure definitions from JSON files for any kind of programming language

Overview Archivist generates data structure definitions from JSON files for any kind of programming language. It also provides a library for golang to

Data Structure Libraries and Algorithms implementation

Algorithms Data Structure Libraries and Algorithms implementation in C++ Disclaimer This repository is meant to be used as a reference to learn data s

Trie data structure implementation in Golang 🌳

Gotri Gotri is an Unicode character based Trie/prefix tree implementation in Go, with the suggestion/auto-complete feature for character searching. Si

Disjoint Set data structure implementation in Go

dsu Implementation of the Disjoint-Set data structure. The Disjoint-Set, Also called a Union-Find or Merge-Find set, is a data structure that stores a

 Data structure,Algorithms implemented in Go (for education)
Data structure,Algorithms implemented in Go (for education)

Data structure,Algorithms implemented in Go (for education) List of Content : 1. Math - 2. String - 3. Conversions - 4. Sort - 5. Search - 6. Data str

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

Implementation of the MaxStack Data Structure in Go

MaxStack-Golang Implementation of the MaxStack Data Structure in Go This repository contains the design of a max stack data structure that supports th

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

Owner
Josh
Josh
Storing strings without GC overhead

stringbank stringbank allows you to hold large numbers of strings without bothering the garbage collector. For small strings storage is reduced as the

Phil Pearl 65 Sep 21, 2022
Package for indexing zip files and storing a compressed index

zipindex zipindex provides a size optimized representation of a zip file to allow decompressing the file without reading the zip file index. It will o

High Performance, Kubernetes Native Object Storage 34 Aug 29, 2022
When storing a value in a Go interface allocates memory on the heap.

Go interface values This repository deep dives Go interface values, what they are, how they work, and when storing a value in a Go interface allocates

Andrew Kutz 29 Sep 15, 2022
Bitset data structure

Your basic bit Set data structure for positive numbers A bit array, or bit set, is an efficient set data structure. It consists of an array that compa

Algorithms to Go 128 Sep 23, 2022
Probabilistic set data structure

Your basic Bloom filter Golang probabilistic set data structure A Bloom filter is a fast and space-efficient probabilistic data structure used to test

Algorithms to Go 74 Sep 26, 2022
Data structure and algorithm library for go, designed to provide functions similar to C++ STL

GoSTL English | 简体中文 Introduction GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more p

stirlingx 714 Sep 23, 2022
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 21 Jul 22, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Derek Parker 605 Sep 23, 2022
BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

Google 2.9k Sep 24, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 652 Sep 15, 2022