datahike.btset — io.replikativ/datahike 0.1.2

B+ tree

Leaf: keys[] :: array of values

Node: pointers[] :: links to children nodes keys[] :: max value for whole subtree node.keys[i] == max(node.pointers[i].keys) All arrays are 64..128 elements, inclusive

BTSet: root :: Node or Leaf shift :: path bit-shift of root level, == (depth - 1) * level-shift cnt :: size of a set, integer, rolling comparator :: comparator used for ordering meta :: clojure meta map __hash :: hash code, same as for clojure collections, on-demand, cached

Path: conceptually a vector of indexes from root to leaf value, but encoded in a single int. E.g. we have path [7 53 11] representing root.pointers[7].pointers[3].keys[11]. In our case level-shift is 8, meaning each index will take 8 bits: (7 << 16) | (53 << 8) | 11 = 472331 0000 0111 0011 0101 0000 1011

Iter: set :: Set this iterator belongs to left :: Current path right :: Right bound path (exclusive) keys :: Cached ref for keys array for a leaf idx :: Cached idx in keys array Keys and idx are cached for fast iteration inside a leaf

-btset-from-seq clj/s

(-btset-from-seq seq cmp)

-btset-from-sorted-arr clj/s

(-btset-from-sorted-arr arr cmp)

-distance clj/s

(-distance node left right level)

-next-path clj/s

(-next-path node path level)

-prev-path clj/s

(-prev-path node path level)

-rpath clj/s

(-rpath node level)

Returns rightmost path possible starting from node and going deeper

-rseek clj/s

(-rseek set key)

Returns path to the first element that is > key. If all elements in a set are <= key, returns (-rpath set) + 1. It’s a virtual path that is bigger than any path in a tree

-seek clj/s

(-seek set key)

Returns path to first element >= key, or -1 if all elements in a set < key

-slice clj/s

(-slice set key-from key-to)

alast clj/s

(alast arr)

alter-btset clj/s

(alter-btset set root shift cnt)

arr-map-inplace clj/s

(arr-map-inplace f arr)

avg-len clj/s

binary-search-l clj/s

(binary-search-l cmp arr r k)

binary-search-r clj/s

(binary-search-r cmp arr r k)

btset clj/s

(btset)

(btset & keys)

BTSet cljs

btset-by clj/s

(btset-by cmp)

(btset-by cmp & keys)

btset-conj clj/s

(btset-conj set key cmp)

btset-disj clj/s

(btset-disj set key cmp)

btset-iter clj/s

(btset-iter set)

Iterator that represents whole set

check-n-splice clj/s

(check-n-splice cmp arr from to new-arr)

cut clj/s

(cut arr cut-from)

(cut arr cut-from cut-to)

cut-n-splice clj/s

(cut-n-splice arr cut-from cut-to splice-from splice-to xs)

distance clj/s

(distance set path-l path-r)

empty-path clj/s

eq-arr clj/s

(eq-arr cmp a1 a1-from a1-to a2 a2-from a2-to)

est-count clj/s

(est-count iter)

half clj/s macro

(half x)

INode clj/s≠ protocol

node-conj clj/s

(node-conj _ cmp key)

node-disj clj/s

(node-disj _ cmp key root? left right)

node-len clj/s

(node-len _)

node-lim-key clj/s

(node-lim-key _)

node-lookup clj/s

(node-lookup _ cmp key)

node-merge clj/s

(node-merge _ next)

node-merge-n-split clj/s

(node-merge-n-split _ next)

insert clj/s

(insert arr idx xs)

Iter cljs

iter clj/s

(iter set left right)

iter-chunk clj/s

(iter-chunk iter)

iter-chunked-next clj/s

(iter-chunked-next iter)

iter-first clj/s

(iter-first iter)

iter-next clj/s

(iter-next iter)

iter-reduce clj/s

(iter-reduce iter f)

(iter-reduce iter f start)

iter-rseq clj/s

(iter-rseq iter)

keys-for clj/s

(keys-for set path)

Leaf cljs

level-shift clj/s

lookup-exact clj/s

(lookup-exact cmp arr key)

lookup-range clj/s

(lookup-range cmp arr key)

max-len clj/s

merge-n-split clj/s

(merge-n-split a1 a2)

min-len clj/s

next-path clj/s

(next-path set path)

Returns path representing next item after path in natural traversal order, or -1 if end of tree has been reached

Node cljs

not== clj/s macro

(not== x y)

path-get clj/s

(path-get path level)

path-mask clj/s

path-set clj/s

(path-set path level idx)

prev-path clj/s

(prev-path set path)

Returns path representing previous item before path in natural traversal order, or -1 if path was already beginning of a tree

return-array clj/s

(return-array a1)

(return-array a1 a2)

(return-array a1 a2 a3)

Drop non-nil references and return array of arguments

ReverseIter cljs

riter clj/s

(riter set left right)

riter-first clj/s

(riter-first riter)

riter-next clj/s

(riter-next ri)

riter-rseq clj/s

(riter-rseq riter)

rotate clj/s

(rotate node root? left right)

slice clj/s

(slice set key)

(slice set key-from key-to)

When called with single key, returns iterator over set that contains all elements equal to the key. When called with two keys (range), returns iterator for all X where key-from <= X <= key-to

splice clj/s

(splice arr splice-from splice-to xs)

uninitialized-hash clj/s