缓存复杂数据的最佳方法

I have a table for storing cost of a voice call according to prefix of the number:

Prefix  ratio 
44      0.01597
447     0.04958
447530  0.03
447531  0.048
447532  0.04950
1       0.1
97      0.1

Finding prefix of a number in table is little complex, because the max matched prefix required. For example
prefix of 4475122112 is 447
and prefix of 4475302112 is 447530

I want to cache the table in memory, to increase performance by reducing the database interactions. As getting prefix of number (and then its rate) need kinda search on the cache

I found two methods:

1. Storing them in a pure map. Search on map can be simple as scanning all of map (maybe lazy).
2. Creating linked list structure as tree. while short prefixes close to root and longest prefix close to leafs.

Now, what is the best way to cache such data? Or is there any other mechanism?

Store them in a map, and try the number whose cost you're looking for. If the number (key) is not in the map, cut off its last digit and repeat. This way if you find a match, guaranteed that will be the longest prefix.

Here's an example lookup function:

var prefixCostMap = map[uint64]float64{
    44:     0.01597,
    447:    0.04958,
    447530: 0.03,
    447531: 0.048,
    447532: 0.04950,
    1:      0.1,
    97:     0.1,
}

func lookup(num uint64) (longestPrefix uint64, cost float64, ok bool) {
    longestPrefix = num

    for longestPrefix > 0 {
        cost, ok = prefixCostMap[longestPrefix]
        if ok {
            break
        }
        longestPrefix = longestPrefix / 10 // Cut off last digit
    }

    return
}

Testing it:

fmt.Println(lookup(4475122112))
fmt.Println(lookup(4475302112))
fmt.Println(lookup(999))

Output (try it on the Go Playground):

447 0.04958 true
447530 0.03 true
0 0 false

Note: this does not support numbers starting with 0. If you also need to handle that, you could store the numbers as string values, so initial 0 digits would be preserved.

This is how the string version looks like:

var prefixCostMap = map[string]float64{
    "44":     0.01597,
    "447":    0.04958,
    "447530": 0.03,
    "447531": 0.048,
    "447532": 0.04950,
    "1":      0.1,
    "97":     0.1,
    "0123":   0.05,
}

func lookup(num string) (longestPrefix string, cost float64, ok bool) {
    longestPrefix = num

    for longestPrefix != "" {
        cost, ok = prefixCostMap[longestPrefix]
        if ok {
            break
        }
        longestPrefix = longestPrefix[:len(longestPrefix)-1] // Cut off last digit
    }

    return
}

Testing it:

fmt.Println(lookup("4475122112"))
fmt.Println(lookup("4475302112"))
fmt.Println(lookup("999"))
fmt.Println(lookup("0123456"))

Output (try it on the Go Playground):

447 0.04958 true
447530 0.03 true
 0 false
0123 0.05 true