Page History: NUB

Compare Page Revisions

141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Current 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

« Older Revision - Back to Page History - Newer Revision »

Page Revision: 2009/02/07 09:28

Download source code: nub-0.3.2.zip
Download API documentation: nub-0.3.0-doc.zip

NUB on SourceForge

NUB is a set of high performance C++ codes providing indexes for variable-length keys, compressed resource files, and an istream interface for blocks of memory. Now supports Unicode keys and up to 17 trillion gigabyte file sizes.


API documentation available online here: http://cnub.org/doc/index.html.

News

2009-02-07: NUB 0.3.2 released. Nodes merged in more cases during key deletion.

2009-02-06: NUB 0.3.1 released. I have addressed the main area where unbalance can occur. During key deletion, sibling nodes are now combined in the majority of cases where this is possible. ResourceFile now combines free areas during deletion also.

2009-02-02: NUB 0.3.0 released. Unicode keys now supported. Generalized Index to a customizable template allowing specification of:

• A KeyInterface to be used for that index.
• index file offset size
• data file offset size
• node size
• node cache size

2009-01-30: NUB 0.2.0 released. Now includes support for huge index and resource files. File offsets are now 64 bits allowing file sizes up to 17 trillion gigabytes.

A Note on NUB Index Files

NUB indexes target storing ASCIIZ variable-length keys to resource files in a highly efficient manner. Because of this requirement, NUB indexes are not B-trees but very similar. B-trees are a variant of M-way branching trees. NUB indexes are not of any particular order M. Instead, each node packs in as many keys as will fit.

2009-01-30: There are currently no special codes to balance the tree during insert and delete so a tree can become badly unbalanced under certain dynamic circumstances. To compensate for this, I am working on a function Index::pack() which will balance the tree and optimize it for fastest access. This would be used once your resource file is complete (prior to release). I should warn you that for very large indexes this function takes a good bit of time.

2009-02-02: Since NUB now supports huge files, I am rethinking the pack() approach. It may be more appropriate to work on the extra codes needed to do some balancing on the fly.

2009-02-07: There are not many more opportunities for improving balance. Performance should be close to that of a B-tree now. In a B-tree, there is no special provision for variable-length keys. NUB indexes are a considerable improvement as far as packing more keys per node. However, NUB indexes are still very similar to B-trees. In general, the focus is on dynamic response to on-the-fly inserts and deletes. Because of this, the nodes of the trees run between half full to full. There is still a need to pack the tree for distribution of a release where there will be little additional modifications to a largely static resource set. Work on IndexT::pack() is in progress.

History

NUB grew out of a start on the Johnny Bashful project. Unfortunately, independent development takes too long these days. The project died for lack of my time to spend on it. It may get resurrected some day. The NUB project is currently undergoing refinement. Support for Unicode keys plus huge index and resource files (64-bit) coming soon (DONE!). Index::pack() is next on the list. I have made one attempt at it, but it resulted in fast but large indexes in some cases. But as I said above, this might not be the best way to go forward from here.