OrderedIndex

public final class OrderedIndex : Codable, @unchecked Sendable

An in-memory sorted array-based index that maps FieldValue keys to posting lists of RecordPointer values.

Architecture choice. This index uses a sorted array with binary search, giving O(log n) point lookups and trivially correct range scans — the same asymptotic performance as a B-tree. An array is significantly simpler to implement, test, and debug. Since the entire index is kept in memory, the O(n) insertion cost of shifting array elements is acceptable for the typical mobile workloads NyaruDB targets (hundreds to low thousands of unique keys).

Persistence is O(n): the entire array is serialised at once using MsgPack and compressed with gzip. For the expected key counts this is negligible.

Class semantics. OrderedIndex is a final class rather than a value type to avoid Swift’s Copy-on-Write (COW) penalties during bulk inserts. With COW, mutating an array-backed value type duplicates the entire internal storage on every mutation, which would make building indexes from a large shard scan quadratic.

Thread safety. The @unchecked Sendable conformance is safe because OrderedIndex is always accessed from within a single CollectionCore actor, which serialises all mutations.

  • The total number of index entries (sum of all posting-list lengths).

    Declaration

    Swift

    public var entryCount: Int { get }

  • The number of unique keys in the index.

    Declaration

    Swift

    public var uniqueKeyCount: Int { get }

  • Undocumented

    Declaration

    Swift

    public init()

  • Declaration

    Swift

    public required init(from decoder: Decoder) throws

Search

  • Returns whether the given key exists in the index.

    Declaration

    Swift

    @inlinable
public func contains(_ key: FieldValue) -> Bool

    Parameters

    key

    The key to look up.

    Return Value

    true if at least one record is indexed under this key.

  • Returns all record pointers indexed under the given key.

    Declaration

    Swift

    @inlinable
public func search(_ key: FieldValue) -> [RecordPointer]

    Parameters

    key

    The key to look up.

    Return Value

    The posting list for that key, or an empty array if the key is not present.

  • Returns all record pointers whose keys fall within the specified range.

    Each bound can be nil (unbounded on that side). The inclusivity of each bound is controlled separately.

    Declaration

    Swift

    @inlinable
public func range(
  lower: FieldValue?, lowerInclusive: Bool,
  upper: FieldValue?, upperInclusive: Bool,
  maxCount: Int? = nil
) -> [RecordPointer]

    Parameters

    lower

    The lower bound, or nil for no lower bound.
    lowerInclusive

    Whether the lower bound is inclusive.
    upper

    The upper bound, or nil for no upper bound.
    upperInclusive

    Whether the upper bound is inclusive.
    maxCount

    Stop after collecting this many pointers (nil = all). Results are collected in ascending key order, so the first maxCount pointers are the lowest-keyed matches.

    Return Value

    The pointers in the range, in ascending key order.

Mutation

  • Inserts a pointer for the given key. If the key already exists, the pointer is appended to its posting list.

    Declaration

    Swift

    public func insert(key: FieldValue, pointer: RecordPointer)

    Parameters

    key

    The index key.
    pointer

    The record pointer to insert.

  • Efficiently loads a batch of index entries in O(n + m) time.

    This method performs a bulk insertion of multiple index entries without causing O(n²) array-shifting overhead. It uses a single-pass merge algorithm that combines existing keys with new entries in one operation.

    The algorithm works as follows:

    1. Sorts incoming entries by key (O(m log m))
    2. Allocates new arrays with pre-calculated capacity (O(1) amortized)
    3. Merges existing and new entries in a single pass (O(n + m))
    4. Groups multiple pointers for duplicate keys

    Complexity

    O(n + m log m) where n is the existing entry count and m is the number of new entries.

    Note

    This method replaces the entire internal storage with newly allocated arrays, which is acceptable for batch operations where the index is being rebuilt. For incremental inserts, prefer insert(key:pointer:).

    See also

    insert(key:pointer:) for single-entry insertion, rebuildAllIndexes() for rebuilding indexes from scratch.

    Declaration

    Swift

    public func bulkLoad(_ entries: [(key: FieldValue, pointer: RecordPointer)])

    Parameters

    entries

    An array of (key: FieldValue, pointer: RecordPointer) tuples representing the new entries to load.

  • Removes a specific pointer from the posting list for the given key. If the posting list becomes empty, the key entry is removed entirely.

    Declaration

    Swift

    public func remove(key: FieldValue, pointer: RecordPointer)

    Parameters

    key

    The index key.
    pointer

    The record pointer to remove.

  • Removes a batch of (key, pointer) entries in a single sweep — the removal analogue of bulkLoad. Removing entries one at a time shifts the tail of the key array on every emptied key, which is quadratic for large batches; this rebuilds the arrays once instead.

    Declaration

    Swift

    public func bulkRemove(_ entries: [(key: FieldValue, pointer: RecordPointer)])

    Parameters

    entries

    The entries to remove. Pointers not present under their key are ignored.

  • Removes every occurrence of the given pointer across all keys in a single pass. Keys whose posting lists become empty are removed.

    Used when a record disappears (stale pointer, corruption) and its index keys are unknown.

    Declaration

    Swift

    public func removeAll(pointer: RecordPointer)

    Parameters

    pointer

    The record pointer to purge from the index.

  • Rewrites pointer offsets after shard compaction using per-shard offset maps, without re-reading or re-parsing any document.

    For every pointer whose shard appears in mapping:

    • If the old offset has a new offset, the pointer is rewritten.
    • If the old offset is absent (the record no longer exists), the stale entry is dropped.

    Pointers into shards not present in mapping are kept unchanged.

    Declaration

    Swift

    public func compactRemap(_ mapping: [String : [UInt64 : UInt64]])

    Parameters

    mapping

    Shard ID → (old offset → new offset).

  • Replaces old pointer with new pointer for a given key.

    Assumes the key has not changed — this is used when a record is updated in place (same key, same shard) and only the file offset changes.

    Declaration

    Swift

    @discardableResult
public func replace(key: FieldValue, old: RecordPointer, new: RecordPointer) -> Bool

    Parameters

    key

    The index key.
    old

    The old pointer to replace.
    new

    The new pointer.

    Return Value

    true if the replacement was performed, false if the old pointer was not found.

Persistence

  • Serialises the index to disk using a hand-rolled binary layout, gzip compression, and optional AES-256-GCM encryption.

    The binary layout is roughly an order of magnitude faster to encode and decode than Codable+MsgPack for large indexes, and it interns shard IDs into a string table so each pointer costs 10 bytes instead of carrying a repeated string:

    "NYI1" | u16 version | u32 shardCount | shardCount × (u16 len + utf8)
u32 keyCount
keyCount × ( FieldValue | u32 postingCount
             | postingCount × (u16 shardIdx + u64 offset) )
FieldValue: u8 tag — 0 null, 1 false, 2 true,
            3 int (+ i64), 4 double (+ f64 bits),
            5 string (+ u32 len + utf8)

    The whole payload is then gzip-compressed and, when a key is provided, AES-GCM sealed — same envelope as before.

    Throws

    NyaruError.encryptionFailed if sealing fails.

    Declaration

    Swift

    public func persist(to url: URL, encryptionKey: SymmetricKey?) throws

    Parameters

    url

    The destination file URL.
    encryptionKey

    Optional AES-256-GCM key.

  • Loads an index from disk, handling decompression and optional decryption.

    Reads the binary snapshot format; snapshots written by older versions (Codable+MsgPack) are decoded through the legacy path, so upgrades do not force an index rebuild.

    Throws

    NyaruError.decryptionFailed if decryption fails, or a decoding error if neither format matches.

    Declaration

    Swift

    public static func load(from url: URL, encryptionKey: SymmetricKey?) throws -> OrderedIndex

    Parameters

    url

    The source file URL.
    encryptionKey

    Optional AES-256-GCM key.

    Return Value

    A fully restored OrderedIndex, or an empty index if the file is empty.