Liking cljdoc? Tell your friends :D

datascript.btset

cljs

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

 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
raw docstring

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close