diff options
| author | Soikk | 2022-08-06 21:46:45 +0200 |
|---|---|---|
| committer | Soikk | 2022-08-06 21:46:45 +0200 |
| commit | f9a7d9cd8a7e603c89d4cc5d98d7f694cc217d85 (patch) | |
| tree | 647b02d6ebabbafed7604da36685b5d17e0c825c /DOC | |
| parent | 0e95d2c61da7b7fbce76b0633313128b7440136e (diff) | |
| download | soikk-DB-f9a7d9cd8a7e603c89d4cc5d98d7f694cc217d85.tar.xz soikk-DB-f9a7d9cd8a7e603c89d4cc5d98d7f694cc217d85.tar.zst | |
Refactored database. Replaced htable with ctable (same thing different name). Introduced AVL tree for hashes.
Diffstat (limited to 'DOC')
| -rw-r--r-- | DOC | 10 |
1 files changed, 10 insertions, 0 deletions
@@ -67,6 +67,16 @@ STORAGE If the relation is already on the table, it returns -1. Otherwise, upon it returns 0 upon completion. Searching for a relation returns the index [0 ... size-1] of said relation in the table, or -1 if its not found. + + AVL trees (tree, or node*) are self-balancing binary search trees used for storing the hashes and the index they store. + Random lookup, insertion and deletion is O(log n), which makes them very well suited for a database. I have chosen AVL trees over B-trees for simplicity. + The height of a node is 1 + the maximum of the height of its left and right children. + The balance of a node is the height of its left child minus the height of its right child. + The rotation, insert and delete functions are explained in + https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ + https://www.geeksforgeeks.org/avl-tree-set-2-deletion/ + + DATABASE |