Documentation ¶
Overview ¶
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.
Example ¶
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) }
Output: key: "Alison" found: true value: "8" key: "foo" found: false value: ""
Example (IndexRanges) ¶
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) }
Output: key: "Aaron" found: true value: "1" key: "Al" found: true value: "2" key: "foo" found: false value: ""
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DataReader ¶
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 ¶
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 ¶
type SlimIndex struct { trie.SlimTrie DataReader }
SlimIndex contains a SlimTrie instance as index and a data provider `DataReader`.
func NewSlimIndex ¶
func NewSlimIndex(index []OffsetIndexItem, dr DataReader) (*SlimIndex, error)
NewSlimIndex creates SlimIndex instance.
The keys in `index` must be in ascending order.