Common Lisp Package: ORG.EBOBBY.BPLUSTREE

README:

FUNCTION

Public

BPLUSTREE-DELETE (KEY TREE)

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

BPLUSTREE-INSERT (RECORD TREE)

Insert a record into the given tree using the given key. Returns the tree with the new record inserted.

BPLUSTREE-INSERT-MANY (TREE &REST ITEMS)

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

BPLUSTREE-NEW (ORDER &KEY (KEY #'IDENTITY) (COMPARER (LAMBDA (N M) (COND ((< N M) -1) ((> N M) 1) (T 0)))))

Makes a new B+ tree with the given order.

BPLUSTREE-SEARCH-RANGE (FROM TO TREE)

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

Private

BPLUSTREE-COMPARER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BPLUSTREE-DEPTH (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BPLUSTREE-KEY (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BPLUSTREE-ORDER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BPLUSTREE-ROOT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BUILD-NODE (ORDER &OPTIONAL (KIND INTERNAL))

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

FIND-LEAF-NODE (NODE KEY)

Find the proper leaf node for the given key.

FIND-NODE (NODE KEY)

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

FIND-RECORD (NODE KEY)

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

MOVE-RECORDS-LEFT (NODE INDEX)

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

MOVE-RECORDS-RIGHT (NODE INDEX)

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

NODE-INTERNAL-P (NODE)

Is the node an internal node?

NODE-KEY-RECORD-SET (NODE N KEY RECORD)

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

NODE-KEYS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-KIND (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-MIN-SIZE (NODE)

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

NODE-NEXT-NODE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-NUM-KEYS (NODE)

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

NODE-ORDER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-OVERFLOW-P (NODE)

Does the node have more records than it should?

NODE-RECORDS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-SIZE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-UNDERFLOW-P (NODE)

Does the node have less records than it should?

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.

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.

Undocumented

SETFBPLUSTREE-COMPARER (NEW-VALUE INSTANCE)

SETFBPLUSTREE-DEPTH (NEW-VALUE INSTANCE)

SETFBPLUSTREE-KEY (NEW-VALUE INSTANCE)

SETFBPLUSTREE-ORDER (NEW-VALUE INSTANCE)

BPLUSTREE-P (OBJECT)

SETFBPLUSTREE-ROOT (NEW-VALUE INSTANCE)

COPY-BPLUSTREE (INSTANCE)

COPY-NODE (INSTANCE)

MAKE-BPLUSTREE (&KEY ((ROOT DUM0) NIL) ((DEPTH DUM1) NIL) ((ORDER DUM2) NIL) ((KEY DUM3) NIL) ((COMPARER DUM4) NIL))

MAKE-NODE (&KEY ((KIND DUM44) NIL) ((ORDER DUM45) NIL) ((SIZE DUM46) NIL) ((KEYS DUM47) NIL) ((RECORDS DUM48) NIL) ((NEXT-NODE DUM49) NIL))

NODE-KEY (NODE I)

NODE-KEY-SET (NODE I VALUE)

NODE-KEY-TRANSFER (SOURCE DESTINATION I-SOURCE I-DESTINATION &KEY SET-SOURCE-NIL)

SETFNODE-KEYS (NEW-VALUE INSTANCE)

SETFNODE-KIND (NEW-VALUE INSTANCE)

SETFNODE-NEXT-NODE (NEW-VALUE INSTANCE)

SETFNODE-ORDER (NEW-VALUE INSTANCE)

NODE-P (OBJECT)

NODE-RECORD (NODE I)

NODE-RECORD-SET (NODE I VALUE)

NODE-RECORD-TRANSFER (SOURCE DESTINATION I-SOURCE I-DESTINATION &KEY SET-SOURCE-NIL)

SETFNODE-RECORDS (NEW-VALUE INSTANCE)

SETFNODE-SIZE (NEW-VALUE INSTANCE)

MACRO

Private

BUILD-NODE-COLLECTION-ACCESORS (COLUMN)

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

BUILD-NODE-COLLECTION-TRANSFER (COLUMN)

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

WITH-COMPARER-FUNCTION (TREE-NAME &BODY BODY)

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

CLASS

Private

Undocumented

BPLUSTREE

NODE