slim: github.com/openacid/slim/index Index | Examples | Files

package index

import "github.com/openacid/slim/index"

Package index provides a data index structure, contains a SlimTrie instance as index and a data provider `DataReader`.

The purpose of `index` is to accelerate accessing external data such as a bunch of key-values on disk.

SlimIndex is an index only, but not a full functional kv-map. The relationship of SlimIndex and its data just like that of B+ tree internal nodes and B+ tree leaf nodes: In a B+ tree only leaf nodes store record. Internal nodes only help on locating a leaf node then a record.

Code:

package main

import (
    "fmt"
    "strings"

    "github.com/openacid/slim/index"
)

type Data string

func (d Data) Read(offset int64, key string) (string, bool) {
    kv := strings.Split(string(d)[offset:], ",")[0:2]
    if kv[0] == key {
        return kv[1], true
    }
    return "", false
}

func main() {

    // Accelerate external data accessing (in memory or on disk) by indexing
    // them with a SlimTrie:

    // `data` is a sample of some unindexed data. In our example it is a comma
    // separated key value series.
    //
    // In order to let SlimTrie be able to read data, `data` should have
    // a `Read` method:
    //     Read(offset int64, key string) (string, bool)
    data := Data("Aaron,1,Agatha,1,Al,2,Albert,3,Alexander,5,Alison,8")

    // keyOffsets is a prebuilt index that stores key and its offset in data accordingly.
    keyOffsets := []index.OffsetIndexItem{
        {Key: "Aaron", Offset: 0},
        {Key: "Agatha", Offset: 8},
        {Key: "Al", Offset: 17},
        {Key: "Albert", Offset: 22},
        {Key: "Alexander", Offset: 31},
        {Key: "Alison", Offset: 43},
    }

    // `SlimIndex` is simply a container of SlimTrie and its data.
    st, err := index.NewSlimIndex(keyOffsets, data)
    if err != nil {
        fmt.Println(err)
    }

    // Lookup
    v, found := st.Get("Alison")
    fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "Alison", found, v)

    v, found = st.Get("foo")
    fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "foo", found, v)

}

Code:

package main

import (
    "fmt"
    "strings"

    "github.com/openacid/slim/index"
)

type RangeData string

func (d RangeData) Read(offset int64, key string) (string, bool) {
    for i := 0; i < 4; i++ {
        if int(offset) >= len(d) {
            break
        }

        kv := strings.Split(string(d)[offset:], ",")[0:2]
        if kv[0] == key {
            return kv[1], true
        }
        offset += int64(len(kv[0]) + len(kv[1]) + 2)

    }
    return "", false
}

func main() {

    // Index ranges instead of keys:
    // In this example at most 4 keys shares one index item.

    data := RangeData("Aaron,1,Agatha,1,Al,2,Albert,3,Alexander,5,Alison,8")

    // keyOffsets is a prebuilt index that stores range start, range end and its offset.
    keyOffsets := []index.OffsetIndexItem{
        // Aaron  +--> 0
        // Agatha |
        // Al     |
        // Albert |

        // Alexander +--> 31
        // Alison    |

        {Key: "Aaron", Offset: 0},
        {Key: "Agatha", Offset: 0},
        {Key: "Al", Offset: 0},
        {Key: "Albert", Offset: 0},

        {Key: "Alexander", Offset: 31},
        {Key: "Alison", Offset: 31},
    }

    st, err := index.NewSlimIndex(keyOffsets, data)
    if err != nil {
        panic(err)
    }

    v, found := st.RangeGet("Aaron")
    fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "Aaron", found, v)

    v, found = st.RangeGet("Al")
    fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "Al", found, v)

    v, found = st.RangeGet("foo")
    fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "foo", found, v)

}

Index

Examples

Package Files

index.go

type DataReader Uses

type DataReader interface {
    // Read value at `offset`, of `key`.
    // Because the internal SlimTrie does not store complete info of a key(to
    // reduce memory consumption).
    // Thus the offset SlimTrie returns might not be correct for an abscent
    // record.
    // It is data providers' responsibility to check if the record at `offset`
    // has the exact `key`.
    Read(offset int64, key string) (string, bool)
}

DataReader defines interface to let SlimIndex access the data it indexes.

type OffsetIndexItem Uses

type OffsetIndexItem struct {
    // Key is the record identity.
    Key string
    // Offset is the position of this record in its storage, E.g. the file offset
    // where this record is.
    Offset int64
}

OffsetIndexItem defines data types for a offset-based index, such as an index of on-disk records.

type SlimIndex Uses

type SlimIndex struct {
    trie.SlimTrie
    DataReader
}

SlimIndex contains a SlimTrie instance as index and a data provider `DataReader`.

func NewSlimIndex Uses

func NewSlimIndex(index []OffsetIndexItem, dr DataReader) (*SlimIndex, error)

NewSlimIndex creates SlimIndex instance.

The keys in `index` must be in ascending order.

func (*SlimIndex) Get Uses

func (si *SlimIndex) Get(key string) (string, bool)

Get returns the value of `key` which is found by `SlimIndex.DataReader`, and a bool value indicating if the `key` is found or not.

func (*SlimIndex) RangeGet Uses

func (si *SlimIndex) RangeGet(key string) (string, bool)

RangeGet returns the value of `key` that is contained in a range, and a bool value indicating if the `key` is found or not.

Package index imports 2 packages (graph). Updated 2020-02-10. Refresh now. Tools for package owners.