Index1024.jl

Documentation for Index1024.jl

Data Types

Index1024.Index — Type

Index

struct to hold the data associated with a particular Index

Properties

meta::Vector{String} user defined meta-data to save in the index file
io::IO the file handle of the index used to navigate

source

Index1024.DataAux — Type

DataAux

Type of the leaf data. (data=UInt64, aux=UInt64)

Named elements

data::UInt64 user supplied
aux::UInt64 user supplied

source

Creating an Index

Index1024.build_index_file — Function

build_index_file(io::IO, kvs; meta=String[])
build_index_file(filename::AbstractString, kvs; meta=String[])

Create the on-disk representation of the index of the kvs Dict. The Leafs are sorted by the key values of the kvs.

Arguments

io::IO descriptor for writing (so you can use IOBuffer if desired)
kvs Dict{UInt64, T}() where T is the type of the leaf, by default DataAux - might expand in future
meta::Vector{AbstractString} vector of strings to add meta data

source

Using an index

Index1024.open_index — Function

open_index(filename::AbstractString)::Index
open_index(io::IO)::Index

Open an Index struct from file on which one can perform searches.

source

Index1024.search — Function

search(idx::Index, search_key::UInt64)::Union{UInt64, Nothing}

Search the given index for a given search_key returning a Tuple of the previously stored value If the search_key is not found, return nothing

Arguments

idx Index to use
search_key UInt64 key to search for

source

Base.get — Function

get(idx::Index, search_key, default)

Search the given index for a given search_key returning a Tuple of the previously stored value or the default

Arguments

idx Index to search
search_key untagged UInt64 key to search for
default what to return if the key is not found

source

Index1024.node_range — Function

node_range(idx::Index, min_key, max_key)

Gather all the Leafs in a given idx where min_key <= key <= max_key

CURRENTLY BROKEN

source

Index1024.todot — Function

todot(idx::Index)

Output the tree in GraphViz dot format. Used for debugging and only includes the root node.

source

Extending the library

Index1024.build_page — Function

build_page(ks, kvs, terminal_tag)

Using the given keys ks use the key/values in ks to generate the tree for this page. The page is the same structure whether the terminals are leafs or "pointers"

Arguments

ks UInt64 keys to write in the terminals (a fixed size per page)
kvs the key / value dictionary containing all of the UInt64 => DataAux pairs
terminal_tag the UInt8 Tag applied to the keys of the terminals

source

Index1024.page_nodes — Function

page_nodes(idx, page, min_key, max_key)

Walk the entire page, a return the leafs and topage Nodes in separate lists

Arguments

idx Index of the tree, needed for io
page first node of the given page
min_key, max_key range of keys for the Leafs wanted

source

Index1024.get_leaf — Function

get_leaf(idx::Index, search_key)

Search the tree for a particular leaf node and return it (or nothing)

Arguments

idx an Index to search
search_key an untagged UInt64 key to search for

source

Index1024.write_pages — Function

write_pages(io, sorted_keys, kvs, terminal_tag; terminal_count=16)

Write the current depth of the tree to disk, depth first. Returns the keys at the root of each page in order and generates the kvs to use as DataAux values

Arguments

io - write into this IO
sorted_keys keys to use in the terminals, in order
kvs Dict of the values to use in the terminals
terminal_tag Tag the terminals with terminal_tag (which will be either leaf or topage)
terminal_count write this many terminals, which might be more than the number of keys

source