🥮 mooncakes.io
README

#core/attr

Attribute indexing strategies for filtered search.

#Strategies

  • Basic: Hash map based indexing
  • Bitmap: Bitmap index for low-cardinality fields
  • BPTree: B+ tree for balanced read/write
  • LSM: Write-optimized with memtable

#Key Types

  • AttrIndexStrategy: Strategy selection enum
  • NumEntry: Sorted entry for numeric index (value, id) pair
  • BasicAttrIndex: Hash map based attribute index
  • BitmapIndex: Bitmap index implementation
  • BPTree: B+ tree index implementation
  • LSMTree: LSM tree with memtable and levels

#Usage

let index = BasicAttrIndex::new()
index.insert("category", @types.String("electronics"), 123L)
let ids = index.find("category", @types.String("electronics"))

#
BPTree

source
type BPTree

B+ Tree structure

#
BPTreeAttrIndex

source
pub struct BPTreeAttrIndex {
  field_trees : Map[String, BPTree]
  exists_trees : Map[String, BPTree]
  data : Map[
VectorId, 
Attrs]
  order : Int
}

B+ Tree Attribute Index container

#
BPTreeAttrIndex::all_ids

source

Return every indexed ID (from the data map).

#
BPTreeAttrIndex::deserialize

source
fn BPTreeAttrIndex::deserialize(data : Bytes) -> BPTreeAttrIndex

Deserialize a B+ tree attribute index from serialized bytes.

Three on-disk layouts are supported (see IdFormat for the history). The legacy v2-tag-byte layout shipped by trkbt10/vcdb <= 0.3.0 is distinguished from the current length-prefixed layout by peeking the first byte of the first VectorId — the two encodings never share a possible first byte, so the choice is unambiguous when data exists. Empty indices default to the current layout.

#
BPTreeAttrIndex::eq

source

Find IDs where key equals value

#
BPTreeAttrIndex::exists

source

Find IDs where key exists

#
BPTreeAttrIndex::get_attrs

source

Get attributes for an ID

#
BPTreeAttrIndex::new

source
fn BPTreeAttrIndex::new(order? : Int) -> BPTreeAttrIndex

Create a new BPTreeAttrIndex

#
BPTreeAttrIndex::range

source

Find IDs matching a numeric range

#
BPTreeAttrIndex::remove_id

source

Remove an ID from the index

#
BPTreeAttrIndex::serialize

source
fn BPTreeAttrIndex::serialize(self : BPTreeAttrIndex) -> Bytes

Serialize a B+ tree attribute index, including node graphs and stored attrs

#
BPTreeAttrIndex::set_attrs

source

Set attributes for an ID

#
BPTreeAttrIndex::size

source
fn BPTreeAttrIndex::size(self : BPTreeAttrIndex) -> Int

Get the number of indexed IDs

#
BasicAttrIndex

source

Basic Attribute Index - Hash map based implementation Provides fast equality lookups and range queries via sorted numeric arrays.

#
BasicAttrIndex::eq

source

Find IDs where key equals value

#
BasicAttrIndex::exists

source

Find IDs where key exists

#
BasicAttrIndex::get_attrs

source

Get attributes for an ID

#
BasicAttrIndex::new

source

Create a new empty BasicAttrIndex

#
BasicAttrIndex::range

source

Find IDs matching a numeric range Returns None if range queries are not supported for this key

#
BasicAttrIndex::remove_id

source

Remove an ID from the index

#
BasicAttrIndex::set_attrs

source

Set attributes for an ID (replaces existing)

#
BasicAttrIndex::size

source
fn BasicAttrIndex::size(self : BasicAttrIndex) -> Int

Get the number of indexed IDs

#
BitmapAttrIndex

source

Bitmap Attribute Index - Simplified index for low-cardinality fields Supports equality and existence queries only, no range queries.

#
BitmapAttrIndex::eq

source

Find IDs where key equals value

#
BitmapAttrIndex::exists

source

Find IDs where key exists

#
BitmapAttrIndex::get_attrs

source

Get attributes for an ID

#
BitmapAttrIndex::new

source

Create a new empty BitmapAttrIndex

#
BitmapAttrIndex::range

source

Range queries not supported for Bitmap index

#
BitmapAttrIndex::remove_id

source

Remove an ID from the index

#
BitmapAttrIndex::set_attrs

source

Set attributes for an ID (replaces existing)

#
BitmapAttrIndex::size

source
fn BitmapAttrIndex::size(self : BitmapAttrIndex) -> Int

Get the number of indexed IDs

#
BloomFilter

source
pub struct BloomFilter {
  bits : Bytes
  hash_count : Int
  bit_count : Int
}

Bloom filter for fast negative lookups

#
BloomFilter::create

source
fn BloomFilter::create(keys : Array[Bytes], false_positive_rate : Double) -> BloomFilter

Create a bloom filter from a set of keys

#
BloomFilter::decode

source
fn BloomFilter::decode(buf : Bytes) -> BloomFilter?

Decode bloom filter from bytes

#
BloomFilter::encode

source
fn BloomFilter::encode(self : BloomFilter) -> Bytes

Encode bloom filter to bytes

#
BloomFilter::might_contain

source
fn BloomFilter::might_contain(self : BloomFilter, key : Bytes) -> Bool

Check if a key might be in the bloom filter

#
LSMAttrIndex

source
pub struct LSMAttrIndex {
  memtable : Memtable
  exists_memtable : Memtable
  data : Map[
VectorId, 
Attrs]
  flush_threshold : Int
}

LSM Index

#
LSMAttrIndex::clear_memtable

source
fn LSMAttrIndex::clear_memtable(self : LSMAttrIndex) -> Unit

Clear memtable (for manual flush)

#
LSMAttrIndex::eq

source

Find IDs where key equals value

#
LSMAttrIndex::exists

source

Find IDs where key exists

#
LSMAttrIndex::get_attrs

source

Get attributes for an ID

#
LSMAttrIndex::memtable_size

source
fn LSMAttrIndex::memtable_size(self : LSMAttrIndex) -> Int

Get memtable size (for flush threshold checking)

#
LSMAttrIndex::new

source
fn LSMAttrIndex::new(flush_threshold? : Int) -> LSMAttrIndex

Create a new LSM attribute index

#
LSMAttrIndex::range

source

Find IDs matching a numeric range Note: Range queries scan through all entries - not optimal for large datasets

#
LSMAttrIndex::remove_id

source

Remove an ID from the index

#
LSMAttrIndex::set_attrs

source

Set attributes for an ID

#
LSMAttrIndex::should_flush

source
fn LSMAttrIndex::should_flush(self : LSMAttrIndex) -> Bool

Check if memtable should be flushed

#
LSMAttrIndex::size

source
fn LSMAttrIndex::size(self : LSMAttrIndex) -> Int

Get the number of indexed IDs

#
Memtable

source
type Memtable

Memtable structure

#
NumEntry

source
pub struct NumEntry {
  value : Double
  id : 
VectorId
}

Sorted entry for numeric index (value, id) pair
impl Show for NumEntry

#
NumEntry::compare

source
fn NumEntry::compare(self : NumEntry, other : NumEntry) -> Int

Compare NumEntry by value for sorting

#
SSTable

source
pub struct SSTable {
  records : Array[SSTableRecord]
  index : Array[SparseIndexEntry]
  bloom : BloomFilter?
  footer : SSTableFooter
}

Decoded SSTable structure (in-memory)

#
SSTable::build

source
fn SSTable::build(records : Array[SSTableRecord], index_interval : Int) -> Bytes

Build an SSTable from sorted records

#
SSTable::find

source
fn SSTable::find(self : SSTable, key : Bytes) -> SSTableRecord?

Find a record in SSTable by key

#
SSTable::read

source
fn SSTable::read(buf : Bytes) -> SSTable?

Read an SSTable from bytes

#
SSTableFooter

source
pub struct SSTableFooter {
  magic : UInt
  version : UInt
  data_offset : Int
  data_size : Int
  index_offset : Int
  index_size : Int
  bloom_offset : Int
  bloom_size : Int
}

SSTable footer structure

#
SSTableFooter::decode

source
fn SSTableFooter::decode(buf : Bytes) -> SSTableFooter?

Decode footer from bytes

#
SSTableFooter::encode

source
fn SSTableFooter::encode(self : SSTableFooter) -> Bytes

Encode footer to bytes

#
SSTableRecord

source
pub struct SSTableRecord {
  key : Bytes
  value : Bytes
}

SSTable record

#
SSTableRecord::decode

source
fn SSTableRecord::decode(buf : Bytes, offset : Int) -> (SSTableRecord, Int)?

Decode a single record from bytes at given offset

#
SSTableRecord::encode

source
fn SSTableRecord::encode(self : SSTableRecord) -> Bytes

Encode a single record to bytes

#
SparseIndexEntry

source
pub struct SparseIndexEntry {
  key : Bytes
  offset : Int
}

Sparse index entry

#
attr_value_to_key

source
fn attr_value_to_key(value : 
AttrValue) -> String

Convert AttrValue to string key for indexing Uses type prefix to disambiguate different types with same string representation

#
attr_value_to_number

source
fn attr_value_to_number(value : 
AttrValue) -> Double?

Extract numeric value from AttrValue for range queries

#
lower_bound

source
fn lower_bound(arr : Array[NumEntry], target : Double) -> Int

Binary search for lower bound in sorted array Returns index of first element >= target

#
remove_num_entry_swap

source
fn remove_num_entry_swap(arr : Array[NumEntry], id : 
VectorId) -> Bool

Remove a NumEntry by id from an array using swap-and-pop Returns true if the entry was found and removed

#
remove_vectorid_swap

source

Remove an Int64 value from an array using swap-and-pop Returns true if the value was found and removed

#
sort_num_entries

source
fn sort_num_entries(arr : Array[NumEntry]) -> Unit

Sort NumEntry array by value

#
upper_bound

source
fn upper_bound(arr : Array[NumEntry], target : Double) -> Int

Binary search for upper bound in sorted array Returns index of first element > target

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io