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.
Source Files
Click to show internal directories.
Click to hide internal directories.