67 karma · joined April 28, 2016
That never happened, but I did drop a couple classes before the withdrawal deadline to fix the workload. It feels so real though.
The Case for Learned Index Structures: https://arxiv.org/abs/1712.01208
Learned Indexes for a Google-scale Disk-based Database: https://arxiv.org/abs/2012.12501
And Noms/Dolt Prolly Trees:
How to Chunk Your Database into a Merkle Tree: https://dolthub.com/blog/2022-06-27-prolly-chunker/
Example: https://go.dev/play/p/as3rT4fB3cn
// Invocation:
strings := []string{"1", "2", "3"}
ints, err := Mapper[string, int](strings).MapErr(strconv.Atoi)
strings = Mapper[string, string](strings).Map(func(s string) string {
return s + "_suffix"
})
// Definition:
type Mapper[T, U any] []T
func (ts Mapper[T, U]) Map(f func(T) U) (us []U) {
us, _ = ts.MapErr(func(t T) (u U, err error) {
u = f(t)
return
})
return
}
func (ts Mapper[T, U]) MapErr(f func(T) (U, error)) (us []U, err error) {
us = make([]U, 0, len(ts))
for _, t := range ts {
var u U
u, err = f(t)
if err != nil {
return
}
us = append(us, u)
}
return
}Whereas Noms Prolly-Trees are like B+Trees, since all values are stored in the leaves.
Merkel Search Trees use the prefix of the hash of inserted keyvalues (number of leading zeros) to determine which layer will contain that keyvalue. This provides a deterministic tree structure for any given set of keyvalues, when you arrange them by key order.
Noms Prolly-Trees use a rolling hash across the sequence of keyvalues to determine split points, similarly when the number of leading zeros exceeds a threshold. Then those leaves are assigned as children to keyvalues on the next highest layer, which is again split in the same way, until a single root node is left.
This one is also a 4-way, haha.