Btree-source-code

A working project for High-concurrency B-tree source code in C. You probably want to download the separate database project for the latest version. Most C files compile under both Windows and Linux.

An idea being investigated in the multi-root-node subdirectory removes the locking load on the root node by creating a read-only copy of the latest updated root version. The root is updated out-of-band.

New B-tree page management code using a skiplist instead of sorted arrays for key searching is under development in a sub-directory. This approach removes the need for a latching protocol for page reading and writing.

Note: The most recent running multi-threaded/multi-process B-tree and ARTree code can be found in a separate repository: https://github.com/malbrain/database.

Here are the projects under btree-source-code:

• btree2: Single Threaded/MultiProcess versions that remove keys all the way back to an original empty btree, placing removed nodes on a free list. Operates under either memory mapping or file I/O. Recommended btrees hosted on network file systems.

• threads2: Multi-Threaded with latching implemented by a latch manager with test & set latches in the first few btree pages.

• threadskv: Multi-Threaded/Multi-Process based on threads2i.c that generalizes key/value storage in the btree pages. The page slots are reduced to 16 or 32 bits, and the value byte storage occurs along with the key storage.