Swiftpack.co - Package - emma-foster/BTree


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



  • Swift 5.1+


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.


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.


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)


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

Other Classes

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

Using BTreeNode


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

Using Storage

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


If the current file used for storage is empty.


Closes the current file of operation.


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)




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.



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


Stars: 3
Help us keep the lights on


Used By

Total: 0


v1.0.0 - Aug 2, 2019

v0.6.1 - Jul 27, 2019

v0.6.0 - Jul 25, 2019

Removed isLeaf and isRoot from storage, making each record stored smaller.

v0.5.0 - Jul 23, 2019

BTree is now a struct rather than a class

  • This has a weird implication that find() is a mutating func, but might be able to work on that in the future
  • Cleaned up consistency throughout BTree
  • Cleaned up storage of root in a new storage
  • Removed parent property of BTreeNode, replaced with isRoot
  • Removed the ability to store duplicate keys
  • Properly save() nodes when they are modified
  • Completely rewrote split(at:), hopefully is much more understandable and swifty now

v0.3.1 - Jul 14, 2019