BTree is a Swift implementation of an on-disk B-Tree, which can store Codable records.

• Requirements
• Installation
• Disclaimer & Warnings
• Design
• Usage
  • Getting Started
  • On minimumDegree
  • Using BTree
  • Other Classes
• Dependencies
• Contributing
• Contact
• Acknowledgements
• License

• Swift 5.1+

dependencies: [
    .package(url: "https://github.com/emma-foster/BTree.git", from: "1.0.0")
]

BTree performs searches and inserts at the expected speed of a B-Tree. BTree uses far more space than expected on disk. BTree does not currently support deletion or updating of records.

This B-Tree implementation is designed to use exclusively Swift, and relies heavily on Codable. I believe that Codable provides a friendly interface for storing and retrieving information from disk & will continue relying on Codable in the future.

This package is essentially split into two parts: BTree and Storage. BTree implements usual B-Tree operations. Storage implements actual storing and retrieving information from disk. In the future, I would like these two parts to be swappable and interchangeable, but I believe currently they are fairly intertwinged. This is definitely future work to be done on this project.

This implementation of B-Tree uses this disk rather than storing the tree in-memory. In-memory data structures provide quick access to small datasets. On-disk implementations like this allow for storing much larger sets of data, while still maintaining relatively quick lookups (though, much slower than in-memory). If your dataset is small, use BTree. However, if your dataset is large, consider this implementation.

import BTree

struct TestKey: Comparable & Codable {
    static func < (lhs: TestKey, rhs: TestKey) -> Bool {
        return lhs.id < rhs.id

    }

    let id: Int

}

struct TestValue: Codable {
    let example: String

}

let tree = BTree<TestKey, TestValue>(storagePath: someFilePath)
let element = BTreeElement<TestKey, TestValue>(key: TestKey(id: 0), value: TestValue(example: "hello"))
try! tree.insert(element)

let element = try! tree.find(element.key)

print(element)

minimumDegree is an argument for BTree which determines the number of elements that can be stored in each node. minimumDegree is exactly minimum degree (Introduction to Algorithms, 3rd Edition, Cormen et al, Section 18.1, page 489). minimumDegree states that the minimum number of elements of a non-root node is minimumDegree - 1, the maximum number of elements of any node is 2 * minimumDegree - 1. Additionally, minimumDegree provides limits on children of a node. Minimum number of children in an internal node: minimumDegree, maximum number of children 2 * minimumDegree. This implementation follows these definitions.

BTree provides operations typical of a search tree.

Find the provided key within the B-Tree. Exactly the same as searching on the root node.

let value = try! tree.find(TestKey(id: 0))

Inserts an element into the B-Tree.

let element = BTreeElement<TestKey, TestValue>(key: TestKey(id: 0), value: TestValue(example: "hello"))
try! tree.insert(element)

These classes are only required to understand the implementation of this B-Tree.

Finds the given key in this node.

let value = try! node.find(TestKey(id: 0))

Inserts an element into this node, if the node is not full.

try! node.insertNonFull(element)

Splits a node a the given child.

try! node.split(at: 0)

Saves a node using the current storage engine

try! node.save()

Loads a node from the current storage engine

try! node.load()

The storage engine for the B-Tree. Interacts with the disk.

If the current file used for storage is empty.

storage.isEmpty()

Closes the current file of operation.

storage.close()

Saves a new root to disk.

let node = BTreeNode<TestKey, TestValue>(minimumDegree: 2, isLeaf: true)
node.id = UUID()
node.isLoaded = true

try! storage.saveRoot(node)

Reads the current root node from disk.

let root = try! storage.readRootNode()

Finds a node on disk.

let node = try! storage.findNode(withOffset: 18)

Appends a node to storage on disk.

try! storage.append(node)

None

This package still requires a lot of work in order to achieve performance characteristics of a B-Tree. This will be the main focus of my contributions to this project. But, there are many other areas of improvement (decoupling BTree and Storage, deletion of elements) and all outside contributions are welcome. Feel free to submit PRs or Issues on this package's GitHub.

Feel free to email questions and comments to emma@emma.sh.

• Introduction to Algorithms, 3rd Edition, which laid out how to implement this B-Tree.
• MicolasLM's bplusthus, for showing me this kind of implementation was possible.
• Swift Algorithm Club's B-Tree implementation for some ideas in how to translate's Intro to Algorithm's psuedocode into Swift.

BTree is released under the MIT license. See LICENSE for details.