BTree Implementation of the `tsearch` facilities

Background

BTree

In short, B-tree is a multi-way tree structure that have bounds of the number of elements in each node. All nodes other than root must be between half full and full.

This is achieved by splitting node on overflow and moving elements or merging node on underflow. From the algorithm, intuitively, we can see the tree is shallow and well-balanced.

BST

While balanced binary tree has the theoretical optimality of the in-memory indexing data structure, it is regarded as less efficient than b-trees in many practical situations, as b-tree usually has lower height and better cache-friendly properties.

In fact, rust’s standard library, abseil-cpp library and many other practical programming libraries decide to implement their ordered set using b-trees instead of red-black trees or AVL trees.

TSearch

Libc’s search library provides

  • tsearch: search or insert elements into a BST
  • tfind: check if an element in within a BST
  • tdelete: remove an element from a BST
  • tdestroy: destroy a BST
  • twalk(_r): perform a DFS walk on a BST and utilize the euler tour information

Idea

Even though the functions are specified as BST management tools; the tree structure is opaque to users, so it is possible to use b-tree as the underlying data structure.

The idea is that b-tree can be interpreted as right-leaning binary trees (just as the red-black tree):


                 =========
                 | 4 | 7 |
       ----------=========----------
       |             |             |
       |             |             |
   =========     =========     =========
   | 1 | 3 |     | 5 |   |     | 8 | 9 |
   =========     =========     =========

   represents
                  __ 4 __
                 |       |
                 |       |
                 1_     _7_
                   |   |   |
                   3   5   8_
                             |
                            9

The problem is that the tsearch/tfind function returns a pointer to the node, which can be used in twalk to do sub-tree DFS (I am not sure the practical usage of this given that the tree implementation is opaque to user; but this is possible according to the POSIX standard). If we store elements directly within the inline storage of node fields, during the insertion and deletion process, the previous returned pointers will become invalid. Thus, we need to allocate a separate cell for each element and make sure the cells are fixed for elements during the tree’s self-balancing process:

  cell
=============
|  data     |
-------------                        ============================
|  node     | ---------------------> | Btree node               |
=============                        |                          |
      ^                              |  ----------------        |
      |                              |  |  |  |  | ... |        |
      |                              |  ----------------        |
      |                              ========|===================
      ----------------------------------------

Experiments

I implemented a btree in C++ but utilize only POD structure and aligned_alloc/memmove/memcpy functions so that is can be imported into libc easily. The implementation is at GitHub - SchrodingerZhu/btree-experiements and the benchmark result can be accessed via btree-experiements/test.ipynb at main · SchrodingerZhu/btree-experiements · GitHub.

The B factor in use was 6, which means 11 elements will trigger the overflow. This is also the choice of the rust standard library.

Even though using cells introduces overhead, btree still performs better in almost all situations. Btree behaves slightly slower in the tree walk; this may be due to the right-leaning binary tree representation increases the “depth”. One good thing is that even the depth of the binary walk is increased, the real recursion stack depth is lower as iterating through a btree node can be implemented in loops.

I also tested btree using binary search as local search strategy. It performs slower than linear search.