Maintaining data in file-systems or databases requires 2 modes; exact-match and near-match. Exact-match retrieves data based on a key. An example is locating a word in a dictionary (e.g. "buffage"; it either exists or it does not). Near-match optionally includes the previous or next key (e.g. "buff" or "buffalo"). NoChop and BTree support both modes.

BTree was chosen to race against NoChop as it is viewed as being the quickest current data-maintenance algorithm. AGD Research considers it to be less of a competitor of NoChop; its' over 600 lines long and requires complex rebalancing logic.

BTree works by building-and-maintaining a tree structure (a BTree). Each node in the tree (which is also a key) connects to 2 others; 1 lesser and 1 greater. BTree then navigates through these nodes until the search-key is located or not (download the white-paper for details of NoChop and BTree from the Downloads web-page).

The accompanying spreadsheet shows the results of the 2 algorithms retrieving 10k passwords, and new tabs and data-sets can easily be created. NoChop's supremacy is already at +100% (2.0 times faster = Mach 2.0). and this is with first-generation, non-optimized code (BTree has benefitted from over 60 years of "tweaking").

The NoChop/STree combination is ideal for massive parallelization, and the accompanying flow-diagram shows one approach. A set of 256 STrees is built, maintained and read. A simple triage would assign a key to a processor based on the first ascii-character of the search-key, for both inputs (adds, updates and deletes) and outputs (reads). A smart one would balance load on a configurable number of processors.

This approach lends itself to augmenting and/or replacing existing ones used to support the back-end of online-and-mobile retail and similar applications. Both SQL (relational) and NoSQL (distributed in-memory) databases can easily incorporate the NoChop/STree combination in their existing architectures.

Maintain imageMaintain image