BTree

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

Contents

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

Requirements

• Swift 5.1+

Installation

Swift Package Manager

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

Disclaimer & Warnings

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.

Design

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.

Why use this B-Tree as opposed to BTree?

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.

Usage

Getting started

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)

On minimumDegree

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.

Using BTree

BTree provides operations typical of a search tree.

find

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))

insert

Inserts an element into the B-Tree.

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

Other Classes

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

Using BTreeNode

find

Finds the given key in this node.

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

insertNonFull

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

try! node.insertNonFull(element)

split

Splits a node a the given child.

try! node.split(at: 0)

save

Saves a node using the current storage engine

try! node.save()

load

Loads a node from the current storage engine

try! node.load()

Using Storage

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

isEmpty

If the current file used for storage is empty.

storage.isEmpty()

close

Closes the current file of operation.

storage.close()

saveRoot

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)

readRootNode

Reads the current root node from disk.

let root = try! storage.readRootNode()

findNode

Finds a node on disk.

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

append

Appends a node to storage on disk.

try! storage.append(node)

Dependencies

None

Contributing

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.

Contact

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

Acknowledgements

• 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.

License

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