Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Announcing my (modest) first library: cl-blustree (in memory B+ tree)
58 views
Skip to first unread message
ebobby
Aug 21, 2012, 3:05:15 PM8/21/12
to
cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.
cl-bplustree is an implementation of a in-memory B+ tree data structure in Common Lisp.
https://github.com/ebobby/cl-bplustree
Dependencies
None.
Usage :
------------------------------------------------------------------------
(bplustree-new (order &key key comparer))
Creates a new empty B+ tre of the given order and returns it.
The key parameter expects a function used to grab the key values (used for sorting) on whatever you are stuffing into the tree, the function will be called with one parameter (a record to be inserted into the tree for example) and it should return the value that will be used as a key. It defaults to #'identity.
The comparer parameter expects a function used when comparing keys against each other in the tree operations. This function has to take two parameters (keys of records) and return a value depending on the following conditions:
(< a b) → -1
(= a b) → 0
(> a b) → 1
The meaning of this of course is given by your particular keys and your particular applications, for string keys for example string<, string>, etc., could be used.
This parameter defaults to a function that implements the explained logic but for numerical keys. If your keys are numeric, you don’t need to supply a comparison function.
Example:
(defparameter *my-tree* (bplustree-new 4 :key (lambda (r) (parse-integer r))))
------------------------------------------------------------------------
(bplustree-insert (record tree))
Inserts the given record into the given tree, if the given key already exists in the tree, the value is updated. Returns the tree but is not needed to capture it and assign it,this call is not destructive on the tree itself, althought its internal elements are changed by it.
Example:
(bplustree-insert "100" *my-tree*)
(bplustree-insert-many (tree &rest items))
Inserts all the records given into the tree. Returns the tree.
Example:
(bplustree-insert-many *my-tree* "5" "10" "-1" "1337" "212" "32" "311" "52")
------------------------------------------------------------------------
(bplustree-search (key tree))
Searches the value stored in the given key in the given tree.
Example:
(bplustree-search 311 *my-tree*) -> "311"
------------------------------------------------------------------------
(bplustree-search-range (from to tree))
Searches the tree for all the records that exists between the given from and to keys and returns them in a list.
Example:
(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "32" "52" "100" "212" "311")
------------------------------------------------------------------------
(bplustree-delete (key tree))
Deletes the record stored in the given key in the tree. Returns the tree but is not needed to capture it and assign it, this call is not destructive on the tree itself, althought its internal elements are changed by it.
Example:
(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "32" "52" "100" "212" "311")
(bplustree-delete 32 *my-tree*)
(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "52" "100" "212" "311")
------------------------------------------------------------------------
PS. Sorry about the repost, the text needed more editing.
cl-bplustree is an implementation of a in-memory B+ tree data structure in Common Lisp.
https://github.com/ebobby/cl-bplustree
Dependencies
None.
Usage :
------------------------------------------------------------------------
(bplustree-new (order &key key comparer))
Creates a new empty B+ tre of the given order and returns it.
The key parameter expects a function used to grab the key values (used for sorting) on whatever you are stuffing into the tree, the function will be called with one parameter (a record to be inserted into the tree for example) and it should return the value that will be used as a key. It defaults to #'identity.
The comparer parameter expects a function used when comparing keys against each other in the tree operations. This function has to take two parameters (keys of records) and return a value depending on the following conditions:
(< a b) → -1
(= a b) → 0
(> a b) → 1
The meaning of this of course is given by your particular keys and your particular applications, for string keys for example string<, string>, etc., could be used.
This parameter defaults to a function that implements the explained logic but for numerical keys. If your keys are numeric, you don’t need to supply a comparison function.
Example:
(defparameter *my-tree* (bplustree-new 4 :key (lambda (r) (parse-integer r))))
------------------------------------------------------------------------
(bplustree-insert (record tree))
Inserts the given record into the given tree, if the given key already exists in the tree, the value is updated. Returns the tree but is not needed to capture it and assign it,this call is not destructive on the tree itself, althought its internal elements are changed by it.
Example:
(bplustree-insert "100" *my-tree*)
(bplustree-insert-many (tree &rest items))
Inserts all the records given into the tree. Returns the tree.
Example:
(bplustree-insert-many *my-tree* "5" "10" "-1" "1337" "212" "32" "311" "52")
------------------------------------------------------------------------
(bplustree-search (key tree))
Searches the value stored in the given key in the given tree.
Example:
(bplustree-search 311 *my-tree*) -> "311"
------------------------------------------------------------------------
(bplustree-search-range (from to tree))
Searches the tree for all the records that exists between the given from and to keys and returns them in a list.
Example:
(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "32" "52" "100" "212" "311")
------------------------------------------------------------------------
(bplustree-delete (key tree))
Deletes the record stored in the given key in the tree. Returns the tree but is not needed to capture it and assign it, this call is not destructive on the tree itself, althought its internal elements are changed by it.
Example:
(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "32" "52" "100" "212" "311")
(bplustree-delete 32 *my-tree*)
(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "52" "100" "212" "311")
------------------------------------------------------------------------
PS. Sorry about the repost, the text needed more editing.
Zach Beane
Aug 21, 2012, 3:11:48 PM8/21/12
to
ebobby <ebo...@gmail.com> writes:
> cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.
>
> cl-bplustree is an implementation of a in-memory B+ tree data
> structure in Common Lisp.
>
> https://github.com/ebobby/cl-bplustree
[snip]
> cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.
>
> cl-bplustree is an implementation of a in-memory B+ tree data
> structure in Common Lisp.
>
> https://github.com/ebobby/cl-bplustree
Looks neat!
Would you consider adding a system file to make it easier to load with
ASDF?
Thanks,
Zach
ebobby
Aug 21, 2012, 3:17:47 PM8/21/12
to
Ah yes, that's next in my todo file. Ill research about it and add it tonight.
Thanks!
Thanks!
Zach Beane
Aug 21, 2012, 3:28:10 PM8/21/12
to
ebobby <ebo...@gmail.com> writes:
> Ah yes, that's next in my todo file. Ill research about it and add it
> tonight.
It's pretty easy. Your file could be as simple as this:
> Ah yes, that's next in my todo file. Ill research about it and add it
> tonight.
;;; cl-bplustree.asd
(asdf:defsystem #:cl-bplustree
:serial t
:components ((:file "packages")
(:file "bplustree")))
Zach
0 new messages