一、背景

提起索引，第一印象就是數(shù)據(jù)庫(kù)的名詞，但是，高斯Redis也可以實(shí)現(xiàn)二級(jí)索引?。?！高斯Redis中的二級(jí)索引一般利用zset來(lái)實(shí)現(xiàn)。高斯Redis相比開(kāi)源Redis有著更高的穩(wěn)定性、以及成本優(yōu)勢(shì)，使用高斯Redis zset實(shí)現(xiàn)業(yè)務(wù)二級(jí)索引，可以獲得性能與成本的雙贏。

索引的本質(zhì)就是利用有序結(jié)構(gòu)來(lái)加速查詢(xún)，因而通過(guò)Zset結(jié)構(gòu)高斯Redis可以輕松實(shí)現(xiàn)數(shù)值類(lèi)型以及字符類(lèi)型索引。

• 數(shù)值類(lèi)型索引（zset按分?jǐn)?shù)排序）：

• 字符類(lèi)型索引（分?jǐn)?shù)相同時(shí)zset按字典序排序）：

下面讓我們切入兩類(lèi)經(jīng)典業(yè)務(wù)場(chǎng)景，看看如何使用高斯Redis來(lái)構(gòu)建穩(wěn)定可靠的二級(jí)索引系統(tǒng)。

二、場(chǎng)景一：詞典補(bǔ)全

當(dāng)在瀏覽器中鍵入查詢(xún)時(shí)，瀏覽器通常會(huì)按照可能性推薦相同前綴的搜索，這種場(chǎng)景可以用高斯Redis二級(jí)索引功能實(shí)現(xiàn)。

2.1 基本方案

最簡(jiǎn)單的方法是將用戶的每個(gè)查詢(xún)添加到索引中。當(dāng)需要進(jìn)行用戶輸入補(bǔ)全推薦時(shí)，使用ZRANGEBYLEX執(zhí)行范圍查詢(xún)即可。如果不希望返回太多條目，高斯Redis還支持使用LIMIT選項(xiàng)來(lái)減少結(jié)果數(shù)量。

• 將用戶搜索banana添加進(jìn)索引：

ZADD myindex 0 banana:1

• 假設(shè)用戶在搜索表單中輸入“bit”，并且我們想提供可能以“bit”開(kāi)頭的搜索關(guān)鍵字。

ZRANGEBYLEX myindex "[bit" "[bit\xff"

即使用ZRANGEBYLEX進(jìn)行范圍查詢(xún)，查詢(xún)的區(qū)間為用戶現(xiàn)在輸入的字符串，以及相同的字符串加上一個(gè)尾隨字節(jié)255（\xff）。通過(guò)這種方式，我們可以獲得以用戶鍵入字符串為前綴的所有字符串。

2.2 與頻率相關(guān)的詞典補(bǔ)全

實(shí)際應(yīng)用中通常希望按照出現(xiàn)頻率自動(dòng)排序補(bǔ)全詞條，同時(shí)可以清除不再流行的詞條，并自動(dòng)適應(yīng)未來(lái)的輸入。我們依然可以使用高斯Redis的ZSet結(jié)構(gòu)實(shí)現(xiàn)這一目標(biāo)，只是在索引結(jié)構(gòu)中，不僅需要存儲(chǔ)搜索詞，還需要存儲(chǔ)與之關(guān)聯(lián)的頻率。

• 將用戶搜索banana添加進(jìn)索引

• 判斷banana是否存在

ZRANGEBYLEX myindex "[banana:" + LIMIT 0 1

• 假設(shè)banana不存在，添加banana:1，其中1是頻率

ZADD myindex 0 banana:1

• 假設(shè)banana存在，需要遞增頻率

若ZRANGEBYLEX myindex "[banana:" + LIMIT 0 1 中返回的頻率為1

1）刪除舊條目：

ZREM myindex 0 banana:1

2）頻率加一重新加入：

ZADD myindex 0 banana:2

請(qǐng)注意，由于可能存在并發(fā)更新，因此應(yīng)通過(guò)Lua腳本發(fā)送上述三個(gè)命令，用Lua script自動(dòng)獲得舊計(jì)數(shù)并增加分?jǐn)?shù)后重新添加條目。

• 假設(shè)用戶在搜索表單中輸入“banana”，并且我們想提供相似的搜索關(guān)鍵字。通過(guò)ZRANGEBYLEX獲得結(jié)果后按頻率排序。

ZRANGEBYLEX myindex "[banana:" + LIMIT 0 10
1) "banana:123"
2) "banaooo:1"
3) "banned user:49"
4) "banning:89"

• 使用流算法清除不常用輸入。從返回的條目中隨機(jī)選擇一個(gè)條目，將其分?jǐn)?shù)減1，然后將其與新分?jǐn)?shù)重新添加。但是，如果新分?jǐn)?shù)為0，我們需從列表中刪除該條目。

• 若隨機(jī)挑選的條目頻率是1，如banaooo:1

ZREM myindex 0 banaooo:1

• 若隨機(jī)挑選的條目頻率大于1，如banana:123

ZREM myindex 0 banana:123
ZADD myindex 0 banana:122

從長(zhǎng)遠(yuǎn)來(lái)看，該索引會(huì)包含熱門(mén)搜索，如果熱門(mén)搜索隨時(shí)間變化，它還會(huì)自動(dòng)適應(yīng)。

三、場(chǎng)景二：多維索引

除了單一維度上的查詢(xún)，高斯Redis同樣支持在多維數(shù)據(jù)中的檢索。例如，檢索所有年齡在50至55歲之間，同時(shí)薪水在70000至85000之間的人。實(shí)現(xiàn)多維二級(jí)索引的關(guān)鍵是通過(guò)編碼將二維的數(shù)據(jù)轉(zhuǎn)化為一維數(shù)據(jù)，再基于高斯Redis zset存儲(chǔ)。

從可視化視角表示二維索引。下圖空間中有一些點(diǎn)，它們代表我們的數(shù)據(jù)樣本，其中x和y是兩個(gè)變量，其最大值均為400。圖片中的藍(lán)色框代表我們的查詢(xún)。我們希望查詢(xún)x介于50和100之間，y介于100和300之間的所有點(diǎn)。

3.1 數(shù)據(jù)編碼

若插入數(shù)據(jù)點(diǎn)為x = 75和y = 200

1）填充0（數(shù)據(jù)最大為400，故填充3位）

x = 075

y = 200

2）交織數(shù)字，以x表示最左邊的數(shù)字，以y表示最左邊的數(shù)字，依此類(lèi)推，以便創(chuàng)建一個(gè)編碼

027050

若使用00和99替換最后兩位，即027000 to 027099，map回x和y，即：

x = 70-79

y = 200-209

因此，針對(duì)x=70-79和y = 200-209的二維查詢(xún)，可以通過(guò)編碼map成027000 to 027099的一維查詢(xún)，這可以通過(guò)高斯Redis的Zset結(jié)構(gòu)輕松實(shí)現(xiàn)。

同理，我們可以針對(duì)后四/六/etc位數(shù)字進(jìn)行相同操作，從而獲得更大范圍。

3）使用二進(jìn)制

為獲得更細(xì)的粒度，可以將數(shù)據(jù)用二進(jìn)制表示，這樣在替換數(shù)字時(shí)，每次會(huì)得到比原來(lái)大二倍的搜索范圍。假設(shè)我們每個(gè)變量?jī)H需要9位（以表示最多400個(gè)值的數(shù)字），我們采用二進(jìn)制形式的數(shù)字將是：

x = 75 -> 001001011

y = 200 -> 011001000

交織后，000111000011001010

讓我們看看在交錯(cuò)表示中用0s ad 1s替換最后的2、4、6、8，...位時(shí)我們的范圍是什么：

3.2 添加新元素

若插入數(shù)據(jù)點(diǎn)為x = 75和y = 200

x = 75和y = 200二進(jìn)制交織編碼后為000111000011001010，

ZADD myindex 0 000111000011001010

3.3 查詢(xún)

查詢(xún)：x介于50和100之間，y介于100和300之間的所有點(diǎn)

從索引中替換N位會(huì)給我們邊長(zhǎng)為2^(N/2)的搜索框。因此，我們要做的是檢查搜索框較小的尺寸，并檢查與該數(shù)字最接近的2的冪，并不斷切分剩余空間，隨后用ZRANGEBYLEX進(jìn)行搜索。

下面是示例代碼：

def spacequery(x0,y0,x1,y1,exp)
    bits=exp*2
    x_start = x0/(2**exp)
    x_end = x1/(2**exp)
    y_start = y0/(2**exp)
    y_end = y1/(2**exp)
    (x_start..x_end).each{|x|
        (y_start..y_end).each{|y|
            x_range_start = x*(2**exp)
            x_range_end = x_range_start | ((2**exp)-1)
            y_range_start = y*(2**exp)
            y_range_end = y_range_start | ((2**exp)-1)
            puts "#{x},#{y} x from #{x_range_start} to #{x_range_end}, y from #{y_range_start} to #{y_range_end}"
            # Turn it into interleaved form for ZRANGEBYLEX query.
            # We assume we need 9 bits for each integer, so the final
            # interleaved representation will be 18 bits.
            xbin = x_range_start.to_s(2).rjust(9,'0')
            ybin = y_range_start.to_s(2).rjust(9,'0')
            s = xbin.split("").zip(ybin.split("")).flatten.compact.join("")
            # Now that we have the start of the range, calculate the end
            # by replacing the specified number of bits from 0 to 1.
            e = s[0..-(bits+1)]+("1"*bits)
            puts "ZRANGEBYLEX myindex [#{s} [#{e}"
        }
    }
end
spacequery(50,100,100,300,6)

四、總結(jié)

本文介紹了如何通過(guò)高斯Redis搭建二級(jí)索引，二級(jí)索引在電商、圖（hexastore）、游戲等領(lǐng)域具有廣泛的應(yīng)用場(chǎng)景，高斯redis現(xiàn)網(wǎng)亦有很多類(lèi)似應(yīng)用。高斯Redis基于存算分離架構(gòu)，依托分布式存儲(chǔ)池確保數(shù)據(jù)強(qiáng)一致，可方便的支持二級(jí)索引功能，為企業(yè)客戶提供穩(wěn)定可靠、超高并發(fā)，且能夠極速?gòu)椥詳U(kuò)容的核心數(shù)據(jù)存儲(chǔ)服務(wù)。

到此這篇關(guān)于使用高斯Redis實(shí)現(xiàn)二級(jí)索引的文章就介紹到這了,更多相關(guān)Redis二級(jí)索引內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！