A binary search cube is a linear data structure that contains a sorted two dimensional dynamic array of nodes which each point to a sorted array of key/value pairs. This creates a three dimensional structure with subsequently three axes. The first two axes function as a lookup table and do not contain any keys. As the axes are of roughly similar size the structure resembles a cube.
The cube can shrink and grow as elements are added. In an ideal situation the axes are of identical size, but it doesn't significantly degrade performance if they are not perfectly matched.
To find a key a binary search is performed on the x axis to find a matching y axis, a second binary search is performed on the y axis to find a matching z axis and a final binary search is performed to find a matching key on the z axis. Each binary search is performed in O(log (cbrt n)) time and the three searches combined are the equivalent of an O(log n) operation.
The term cbrt stands for cube root.
Inserting or removing a node is an O(cbrt n) operation. If a node falls between two Z axes the search algorithm can be optimized to pick the lower order axis so the node is appended to the end, which is a faster operation. As a consequence a node will never be inserted on the 0 index with the exception of the floor axis.
The special case of a floor insertion can be checked at the start of the binary search, subsequent binary searches on the X, Y and Z axes can be optimized to deference the 0 index check.
The most efficient search approach appears to be a binary search using deferred detection of equality. Notably the detection of equality can be skipped for the X and Y axis.
In order to increase the access speed each axis can remember the floor key, which is all that is needed to perform a binary search using deferred detection of equality on the lower axes. Alternatively a cube of floor keys can be maintained, which results in better cache utilization.
Balancing a binary search cube is fairly simple. When adding a node to the Z axis and it exceeds twice the size of the X axis the Z axis is split. If this results in the underlying Y axis exceeding twice the size of the X axis the Y axis is split. These are O(cbrt n) operations.
It can be detected whether the cube is imbalanced by comparing the volume to the optimal volume. Shrinking an Y axis is a fast operation that is required infrequently at regular intervals.
Using a binary search cube as a priority queue
A binary search cube can be optimized to check the last index first, allowing O(1) push and pop operations.
Alternatively the last index of each axis can be checked first when performing a binary search. This allows O(m) push and pull operations, where m is the number of dimensions of the cube.
A binary search cube has less memory overhead than a binary search tree. A cube with 1,000,000 elements will have 100 X nodes and 10,000 Y nodes. A binary search tree of the same size requires 2,000,000 leaf node pointers, with some implementations requiring an additional 1,000,000 root node pointers.
The toll of insert and resize operations on large cubes can be reduced by using a hyper cube. The maximum length of an axis is set at 16 (or 32) and whenever the maximum volume is exhausted an extra dimension is added. The hyper cube starts out as a 1 dimensional array, turning into a 2 dimensional binary search square when the 17th element is added. When the 257th element is added the binary search square is split into a binary search cube with 3 dimensions, though this split can happen at the 129th element depending on the distribution. When the 65537th element is added the cube turns into a 4 dimensional tesseract. And so on.
Using static axis sizes will eliminate the need to resize Z axes as the cube grows and the average insertion (moving 8 elements) will become faster than O(log n) once a size of 256 elements is reached.
Looking up an index is an O(log n) operation, which would be the main advantage, and possibly the only advantage as there would be several drawbacks.
Cubesort
It's also possible to have no memory requirements at all and use 5 scandir() calls to find a file.
Parallel Cubesort
As sorting partially sorted data with cubesort is substantially faster it's possible to divide the data in blocks of 100,000 elements and sort these in parallel, while the main process sorts the pre-sorted blocks one at a time.
Mergesort is poorly suited for this approach, especially when trying to merge 100K elements into a larger 10M elements array.
The lower axes can be given a fixed maximum size. The Z axes can be given a size of 32, the Y axes a size of 64, the X axes a size of 128, with the W axis of variable size. This type of search tesseract (4 dimensions) doesn't require resizing as it grows, has reasonable performance for both smaller and larger sizes, and allows fast insertions.
Resizing the search tesseract as it shrinks is optional and can be handled by keeping the average Z axis length above 8.
If the key size is fixed (typically when the key is an integer) it's possible to implement a cube as a trie. A binary search is used to find a key fragment, with the exception that a key fragment can be found in O(1) time when it falls within the section of the axis that is in order.
When using this approach resizing is never necessary. Subsequently ideal distribution isn't guaranteed.
Iterating a binary search cube
Iterating is similar to iterating a multi-dimensional array. The main problem is how to handle changes to the cube during iteration. As a solution a global state can be introduced that is checked whenever an element is added or removed. Tree structures have the same problem but are much more robust.