search

elastic / elasticsearch

Free and Open, Distributed, RESTful Search Engine
https://www.elastic.co/products/elasticsearch
Other
68.51k stars 24.33k forks source link

Big Array Backed Balanced Binary Trees #95960

Open not-napoleon opened 1 year ago

not-napoleon commented 1 year ago

Description

In https://github.com/elastic/elasticsearch/pull/95809 we prototyped a sorted keys iterator for LongKeyedBucketOrds, using a Java TreeSet. Using a tree set here has many benefits, notably logarithmic insertion time, and a naturally sorted iterator. However, the use of the Java Collections implementation means the memory used for this isn't tracked in our circuit breaker. To solve this, I propose building a data structure with the beneficial properties of a tree set, backed by a BigArray.

elasticsearchmachine commented 1 year ago

Pinging @elastic/es-analytics-geo (Team:Analytics)