The cl-bplustree Reference Manual

This is the cl-bplustree Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed May 15 03:45:57 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 cl-bplustree

In-memory B+ tree

Author

Francisco Soto <>

License

BSD

Source

cl-bplustree.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 cl-bplustree/cl-bplustree.asd

Source

cl-bplustree.asd.

Parent Component

cl-bplustree (system).

ASDF Systems

cl-bplustree.


3.1.2 cl-bplustree/packages.lisp

Source

cl-bplustree.asd.

Parent Component

cl-bplustree (system).

Packages

org.ebobby.bplustree.


3.1.3 cl-bplustree/bplustree.lisp

Dependency

packages.lisp (file).

Source

cl-bplustree.asd.

Parent Component

cl-bplustree (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 org.ebobby.bplustree

Source

packages.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Ordinary functions

Function: bplustree-delete (key tree)

Deletes a record from the given tree using the given key. Returns the tree with the record deleted.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-empty-p (tree)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-insert (record tree &optional key)

Insert a record into the given tree using the given key. Returns the tree with the new record inserted. If ‘key‘ is included, uses that instead of calling the key function on ‘record‘.
This enabled using the tree as a key/value store instead of a sorted set.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-insert-many (tree &rest items)

Insert as many records given into the tree. Returns the tree with the new records inserted.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-new (order &key key comparer)

Makes a new B+ tree with the given order.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-search (key tree)

Search for a record in the given tree using the given key.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-search-next (key tree)

Return the first key in ‘tree‘ after the passed ‘key‘. Return the record as a second value.
If the third values is true, then the key and value were cached.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-search-prev (key tree)

Return the key in ‘tree‘ before the passed ‘key‘.
Return the record as a second value.
If the third values is true, then the key and value were cached.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-search-range (from to tree)

Search and return a range of records in the given tree between the given keys.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-traverse (tree fn)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-traverse-with-keys (tree fn)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.


5.1.2 Standalone methods

Method: print-object ((tree bplustree) str)
Source

bplustree.lisp.


5.2 Internals


5.2.1 Macros

Macro: build-node-collection-accesors (column)

Generates the getter/setter functions for the btreeplus-node internal collections, keys and records.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Macro: build-node-collection-transfer (column)

Generates functions to transfer elements from a node into another node.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Macro: with-comparer-function (tree-name &body body)

Wrap code inside a block that will create a dynamic variable that holds the comparer function.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.


5.2.2 Ordinary functions

Reader: bplustree-cache (instance)
Writer: (setf bplustree-cache) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

cache.

Reader: bplustree-comparer (instance)
Writer: (setf bplustree-comparer) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

comparer.

Reader: bplustree-depth (instance)
Writer: (setf bplustree-depth) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

depth.

Reader: bplustree-key (instance)
Writer: (setf bplustree-key) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

key.

Reader: bplustree-order (instance)
Writer: (setf bplustree-order) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

order.

Function: bplustree-p (object)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Reader: bplustree-root (instance)
Writer: (setf bplustree-root) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

root.

Function: bplustree-traverse-node (node fn)

Call ‘fn‘ on each leaf record in ‘node‘.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: bplustree-traverse-node-with-keys (node fn)

Call ‘fn‘ with key and record for each leaf of ‘node‘.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: build-node (order &optional kind)

Makes an empty B+ tree node with the given order and the optional type (:leaf or :internal).

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: copy-bplustree (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: copy-node (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: find-leaf-node (node key)

Find the proper leaf node for the given key.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: find-node (node key)

Get the next node using the given key in the given node.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: find-record (node key)

Get the record with the given key in the given node, nil if none.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: make-bplustree (&key root depth order key comparer cache)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: make-node (&key kind order size keys records prev-node next-node)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: move-records-left (node index)

Move the keys and records going left to right from given starting point.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: move-records-right (node index)

Move the keys and records from the given starting point to the right.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-internal-p (node)

Is the node an internal node?

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-key (node i)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-key-record-set (node n key record)

Sets both the key and record at the given index to the given B+ node.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-key-set (node i value)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-key-transfer (source destination i-source i-destination &key set-source-nil)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Reader: node-keys (instance)
Writer: (setf node-keys) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

keys.

Reader: node-kind (instance)
Writer: (setf node-kind) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

kind.

Function: node-min-size (node)

Returns the minimum size a node can have (except root).

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Reader: node-next-node (instance)
Writer: (setf node-next-node) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

next-node.

Function: node-num-keys (node)

Get the number of keys based on the node size and node type.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Reader: node-order (instance)
Writer: (setf node-order) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

order.

Function: node-overflow-p (node)

Does the node have more records than it should?

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-p (object)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Reader: node-prev-node (instance)
Writer: (setf node-prev-node) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

prev-node.

Function: node-record (node i)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-record-set (node i value)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: node-record-transfer (source destination i-source i-destination &key set-source-nil)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Reader: node-records (instance)
Writer: (setf node-records) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

records.

Reader: node-size (instance)
Writer: (setf node-size) (instance)
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Target Slot

size.

Function: node-underflow-p (node)

Does the node have less records than it should?

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: promote-first-key (node &key no-shift)

Promotes the first key in the node, if its a leaf it simply returns it, if its an internal node it returns it but shifts the other keys to the left.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Function: search-node-keys (node key &key record-search)

Search the given node keys vector using binary search.
Keys assumed to be sorted. Optional mix and max define the search space. The keyword record-search indicates if you are looking for a record or a node.

Package

org.ebobby.bplustree.

Source

bplustree.lisp.


5.2.3 Structures

Structure: bplustree
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: root
Readers

bplustree-root.

Writers

(setf bplustree-root).

Slot: depth
Readers

bplustree-depth.

Writers

(setf bplustree-depth).

Slot: order
Readers

bplustree-order.

Writers

(setf bplustree-order).

Slot: key
Readers

bplustree-key.

Writers

(setf bplustree-key).

Slot: comparer
Readers

bplustree-comparer.

Writers

(setf bplustree-comparer).

Slot: cache
Readers

bplustree-cache.

Writers

(setf bplustree-cache).

Structure: node
Package

org.ebobby.bplustree.

Source

bplustree.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: kind
Readers

node-kind.

Writers

(setf node-kind).

Slot: order
Readers

node-order.

Writers

(setf node-order).

Slot: size
Readers

node-size.

Writers

(setf node-size).

Slot: keys
Readers

node-keys.

Writers

(setf node-keys).

Slot: records
Readers

node-records.

Writers

(setf node-records).

Slot: prev-node
Readers

node-prev-node.

Writers

(setf node-prev-node).

Slot: next-node
Readers

node-next-node.

Writers

(setf node-next-node).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
B   C   F   M   N   P   S   W  
Index Entry  Section

(
(setf bplustree-cache): Private ordinary functions
(setf bplustree-comparer): Private ordinary functions
(setf bplustree-depth): Private ordinary functions
(setf bplustree-key): Private ordinary functions
(setf bplustree-order): Private ordinary functions
(setf bplustree-root): Private ordinary functions
(setf node-keys): Private ordinary functions
(setf node-kind): Private ordinary functions
(setf node-next-node): Private ordinary functions
(setf node-order): Private ordinary functions
(setf node-prev-node): Private ordinary functions
(setf node-records): Private ordinary functions
(setf node-size): Private ordinary functions

B
bplustree-cache: Private ordinary functions
bplustree-comparer: Private ordinary functions
bplustree-delete: Public ordinary functions
bplustree-depth: Private ordinary functions
bplustree-empty-p: Public ordinary functions
bplustree-insert: Public ordinary functions
bplustree-insert-many: Public ordinary functions
bplustree-key: Private ordinary functions
bplustree-new: Public ordinary functions
bplustree-order: Private ordinary functions
bplustree-p: Private ordinary functions
bplustree-root: Private ordinary functions
bplustree-search: Public ordinary functions
bplustree-search-next: Public ordinary functions
bplustree-search-prev: Public ordinary functions
bplustree-search-range: Public ordinary functions
bplustree-traverse: Public ordinary functions
bplustree-traverse-node: Private ordinary functions
bplustree-traverse-node-with-keys: Private ordinary functions
bplustree-traverse-with-keys: Public ordinary functions
build-node: Private ordinary functions
build-node-collection-accesors: Private macros
build-node-collection-transfer: Private macros

C
copy-bplustree: Private ordinary functions
copy-node: Private ordinary functions

F
find-leaf-node: Private ordinary functions
find-node: Private ordinary functions
find-record: Private ordinary functions
Function, (setf bplustree-cache): Private ordinary functions
Function, (setf bplustree-comparer): Private ordinary functions
Function, (setf bplustree-depth): Private ordinary functions
Function, (setf bplustree-key): Private ordinary functions
Function, (setf bplustree-order): Private ordinary functions
Function, (setf bplustree-root): Private ordinary functions
Function, (setf node-keys): Private ordinary functions
Function, (setf node-kind): Private ordinary functions
Function, (setf node-next-node): Private ordinary functions
Function, (setf node-order): Private ordinary functions
Function, (setf node-prev-node): Private ordinary functions
Function, (setf node-records): Private ordinary functions
Function, (setf node-size): Private ordinary functions
Function, bplustree-cache: Private ordinary functions
Function, bplustree-comparer: Private ordinary functions
Function, bplustree-delete: Public ordinary functions
Function, bplustree-depth: Private ordinary functions
Function, bplustree-empty-p: Public ordinary functions
Function, bplustree-insert: Public ordinary functions
Function, bplustree-insert-many: Public ordinary functions
Function, bplustree-key: Private ordinary functions
Function, bplustree-new: Public ordinary functions
Function, bplustree-order: Private ordinary functions
Function, bplustree-p: Private ordinary functions
Function, bplustree-root: Private ordinary functions
Function, bplustree-search: Public ordinary functions
Function, bplustree-search-next: Public ordinary functions
Function, bplustree-search-prev: Public ordinary functions
Function, bplustree-search-range: Public ordinary functions
Function, bplustree-traverse: Public ordinary functions
Function, bplustree-traverse-node: Private ordinary functions
Function, bplustree-traverse-node-with-keys: Private ordinary functions
Function, bplustree-traverse-with-keys: Public ordinary functions
Function, build-node: Private ordinary functions
Function, copy-bplustree: Private ordinary functions
Function, copy-node: Private ordinary functions
Function, find-leaf-node: Private ordinary functions
Function, find-node: Private ordinary functions
Function, find-record: Private ordinary functions
Function, make-bplustree: Private ordinary functions
Function, make-node: Private ordinary functions
Function, move-records-left: Private ordinary functions
Function, move-records-right: Private ordinary functions
Function, node-internal-p: Private ordinary functions
Function, node-key: Private ordinary functions
Function, node-key-record-set: Private ordinary functions
Function, node-key-set: Private ordinary functions
Function, node-key-transfer: Private ordinary functions
Function, node-keys: Private ordinary functions
Function, node-kind: Private ordinary functions
Function, node-min-size: Private ordinary functions
Function, node-next-node: Private ordinary functions
Function, node-num-keys: Private ordinary functions
Function, node-order: Private ordinary functions
Function, node-overflow-p: Private ordinary functions
Function, node-p: Private ordinary functions
Function, node-prev-node: Private ordinary functions
Function, node-record: Private ordinary functions
Function, node-record-set: Private ordinary functions
Function, node-record-transfer: Private ordinary functions
Function, node-records: Private ordinary functions
Function, node-size: Private ordinary functions
Function, node-underflow-p: Private ordinary functions
Function, promote-first-key: Private ordinary functions
Function, search-node-keys: Private ordinary functions

M
Macro, build-node-collection-accesors: Private macros
Macro, build-node-collection-transfer: Private macros
Macro, with-comparer-function: Private macros
make-bplustree: Private ordinary functions
make-node: Private ordinary functions
Method, print-object: Public standalone methods
move-records-left: Private ordinary functions
move-records-right: Private ordinary functions

N
node-internal-p: Private ordinary functions
node-key: Private ordinary functions
node-key-record-set: Private ordinary functions
node-key-set: Private ordinary functions
node-key-transfer: Private ordinary functions
node-keys: Private ordinary functions
node-kind: Private ordinary functions
node-min-size: Private ordinary functions
node-next-node: Private ordinary functions
node-num-keys: Private ordinary functions
node-order: Private ordinary functions
node-overflow-p: Private ordinary functions
node-p: Private ordinary functions
node-prev-node: Private ordinary functions
node-record: Private ordinary functions
node-record-set: Private ordinary functions
node-record-transfer: Private ordinary functions
node-records: Private ordinary functions
node-size: Private ordinary functions
node-underflow-p: Private ordinary functions

P
print-object: Public standalone methods
promote-first-key: Private ordinary functions

S
search-node-keys: Private ordinary functions

W
with-comparer-function: Private macros