曹衛(wèi)東，金 超

(中國民航大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

索引作為如今數(shù)據(jù)庫系統(tǒng)中用于數(shù)據(jù)存儲的重要技術(shù)之一，直接影響到了數(shù)據(jù)庫系統(tǒng)的存取性能。幾十年來，研究人員致力于研究出輕量、高效的索引結(jié)構(gòu)：部分學(xué)者通過優(yōu)化B樹索引結(jié)構(gòu)和嘗試索引壓縮算法[1]來更好地發(fā)揮包括CPU緩存等在內(nèi)的硬件優(yōu)勢，例如A-樹[2]在葉子節(jié)點(diǎn)中使用了線性模型。

傳統(tǒng)數(shù)據(jù)庫索引為了追求泛用性，通常只通過數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，欠缺對數(shù)據(jù)集模式和分布規(guī)律的考慮[3]。Google團(tuán)隊Kraska等[4]將機(jī)器學(xué)習(xí)引入索引結(jié)構(gòu)設(shè)計，并提出了learned index。這種索引結(jié)構(gòu)可以學(xué)習(xí)數(shù)據(jù)集分布情況，生成適配度較高的專用索引結(jié)構(gòu)，顯著提升大數(shù)據(jù)檢索效率[5]。

Michael Mitzenmacher將神經(jīng)網(wǎng)絡(luò)運(yùn)用在數(shù)據(jù)庫索引布隆過濾器上[6]，Harrie Oosterhuis等研究了機(jī)器學(xué)習(xí)索引在索引壓縮上的潛力[7]，HaiXin Wang等嘗試用機(jī)器學(xué)習(xí)化的索引結(jié)構(gòu)檢索高維數(shù)據(jù)[8]，混合專家網(wǎng)絡(luò)[9]等技術(shù)也被引入相關(guān)研究。但是索引更新的問題沒有得到解決，針對這一缺陷，JiaLin Ding等[10]提出了ALEX，對葉節(jié)點(diǎn)進(jìn)行了重新設(shè)計，使用就地插入策略解決了之前l(fā)earned index只能在只讀場景下進(jìn)行的問題。并發(fā)數(shù)據(jù)結(jié)構(gòu)XIndex索引[11]采取的解決方案是設(shè)置緩沖區(qū)進(jìn)行插入。FITling-tree[12]為每個段內(nèi)部預(yù)留緩沖區(qū)實(shí)現(xiàn)更新。PGM-index[13]從索引壓縮等多個方面優(yōu)化了FITing-Tree。但是大多數(shù)相關(guān)研究選擇采用learned index提出的遞歸模型Recursive Model Indexes(RMI)結(jié)構(gòu)框架或類似RMI結(jié)構(gòu)框架，并沒有解決RMI中數(shù)據(jù)固定劃分導(dǎo)致擬合效果不佳和訓(xùn)練時間長的問題。

本文面向海量數(shù)據(jù)高檢索需求，提出了ULIB (upda-table learning index structure based on birch clustering)。該模型采用了類樹的結(jié)構(gòu)設(shè)計，首先對數(shù)據(jù)集使用birch聚類算法來實(shí)現(xiàn)數(shù)據(jù)的初步劃分，引入Calinski-Harabasz(CH)函數(shù)作為評價指標(biāo)判斷聚類有效性；然后在訓(xùn)練階段，采用前饋神經(jīng)網(wǎng)絡(luò)進(jìn)行分段學(xué)習(xí)，同時將數(shù)據(jù)訪問模式引入損失函數(shù)設(shè)計提高預(yù)測精度。最后，在數(shù)據(jù)更新過程中使用基于日志結(jié)構(gòu)合并(log-structured merge，LSM)樹的異地插入策略解決更新問題。

1 機(jī)器學(xué)習(xí)索引

1.1 機(jī)器學(xué)習(xí)索引模型及相關(guān)問題

機(jī)器學(xué)習(xí)索引模型使用索引列的所有鍵值作為訓(xùn)練集進(jìn)行訓(xùn)練，待檢索數(shù)據(jù)鍵作為輸入，鍵值所在的位置作為輸出。訓(xùn)練結(jié)束得到的模型會生成真實(shí)值的偏移量，并存儲整個數(shù)據(jù)集中最大的向下和向上偏移量(稱作誤差范圍)。如圖1所示，B樹等同于機(jī)器學(xué)習(xí)，同樣可以看成一個根據(jù)鍵值預(yù)測數(shù)據(jù)所在位置的模型。

圖1 B樹與機(jī)器學(xué)習(xí)索引結(jié)構(gòu)

當(dāng)機(jī)器學(xué)習(xí)索引模型中一個檢索請求生成后，模型根據(jù)輸入的鍵值輸出這個鍵對應(yīng)數(shù)據(jù)項(xiàng)的預(yù)測位置，類似B樹中的頁面設(shè)置，數(shù)據(jù)檢索保證了在預(yù)測位置最大的上下誤差范圍內(nèi)一定能搜索到待檢索的數(shù)據(jù)項(xiàng)。雖然在索引設(shè)計方案中使用一個全連接神經(jīng)網(wǎng)絡(luò)就可以擬合數(shù)據(jù)的整體分布，但是由于索引對于預(yù)測精度的要求較高，訓(xùn)練階段需要大量的時間和空間去降低極小的誤差，即在單個數(shù)據(jù)實(shí)例級別上進(jìn)行精確定位十分困難[14]，這個問題被稱作是“最后一公里”問題。

可以說，機(jī)器學(xué)習(xí)索引設(shè)計的關(guān)鍵就是如何解決初始數(shù)據(jù)劃分問題、數(shù)據(jù)劃分后的“最后一公里”問題和索引更新問題。

1.2 learned index的解決方案

learned index提供的解決方案是RMI，其結(jié)構(gòu)如圖2所示。

圖2 RMI模型結(jié)構(gòu)

其中，RMI頂層使用神經(jīng)網(wǎng)絡(luò)來實(shí)現(xiàn)數(shù)據(jù)分發(fā)，在第二層使用線性回歸算法來實(shí)現(xiàn)各數(shù)據(jù)段的擬合，除第一層外，每一層分布情況由上一層模型的輸出決定，遞歸執(zhí)行直至最后一層，在誤差區(qū)間使用二分查找來找到待檢索鍵的最終位置。

learned index相比較B樹，在查詢時間復(fù)雜度方面，可以由B樹的O(logN)降低至O(1)，同時也可以顯著減少空間占用，空間復(fù)雜度從B樹O(N)降低至O(1)。

learned index存在的問題為：使用復(fù)雜的遞歸層次結(jié)構(gòu)帶來的模型訓(xùn)練時間長的問題；采取均等劃分策略進(jìn)行數(shù)據(jù)劃分，葉子節(jié)點(diǎn)使用線性回歸模型進(jìn)行擬合解決“最后一公里”問題，擬合效果很大程度上由數(shù)據(jù)劃分階段所劃分出的各個數(shù)據(jù)區(qū)域自身分布決定，性能存在優(yōu)化空間；每次數(shù)據(jù)更新后需要完整重新訓(xùn)練數(shù)據(jù)集，即沒有解決索引更新的問題。

2 可更新機(jī)器學(xué)習(xí)索引模型ULIB

針對大數(shù)據(jù)時代海量數(shù)據(jù)高檢索需求，提出基于birch聚類的高效可更新機(jī)器學(xué)習(xí)索引模型ULIB。

2.1 ULIB模型結(jié)構(gòu)

ULIB模型結(jié)構(gòu)如圖3所示，模型一共分為4個階段：

圖3 ULIB模型結(jié)構(gòu)

(1)數(shù)據(jù)劃分，利用birch算法將數(shù)據(jù)集劃分為D1到Dk，由于在神經(jīng)網(wǎng)絡(luò)中訓(xùn)練時間并不隨數(shù)據(jù)集規(guī)模增長而線性增加，而是更高程度增長，所以劃分?jǐn)?shù)據(jù)集的操作可以獲得更短的訓(xùn)練時間；

(2)基于神經(jīng)網(wǎng)絡(luò)的葉子結(jié)點(diǎn)訓(xùn)練，針對數(shù)據(jù)劃分后的k個數(shù)據(jù)區(qū)域，分別構(gòu)建同樣數(shù)量的神經(jīng)網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，以解決“最后一公里”問題。

(3)數(shù)據(jù)檢索，當(dāng)查詢數(shù)據(jù)時，模型選擇器首先檢查待查詢鍵是否存在于緩存中，若不在則確定出待查詢鍵所對應(yīng)的模型和鍵所在位置的預(yù)測y，最后自預(yù)測位置y按照最大最小誤差利用二分查找展開搜索，直至找到最終的數(shù)據(jù)精確位置。

(4)數(shù)據(jù)更新，當(dāng)數(shù)據(jù)插入時，模型會在內(nèi)存中開辟一個緩存區(qū)域存儲待插入數(shù)據(jù)，當(dāng)緩存溢出時，將緩存中所有數(shù)據(jù)插入到對應(yīng)學(xué)習(xí)模型中，并重新訓(xùn)練對應(yīng)模型。

2.2 基于birch聚類的數(shù)據(jù)劃分

2.2.1 birch聚類及有效性判定

birch算法是一種自底向上的層次聚類算法，核心為聚類特征CF和聚類特征樹CFtree。

相比較k-means，birch聚類無需定義聚類特征數(shù)k，且能以很高的效率更新[15]。CFtree包含3個關(guān)鍵閾值數(shù)，每個內(nèi)部節(jié)點(diǎn)的最大CF閾值數(shù)B、葉節(jié)點(diǎn)最大CF閾值數(shù)L和子簇最大半徑閾值T，這3個數(shù)值直接決定了CFtree的最終形態(tài)和聚類類別數(shù)。

一般來說，在沒有數(shù)據(jù)集類別的先驗(yàn)知識時，需要確定出合適的B、L和T來使聚類效果盡可能好。研究者提出了“最優(yōu)聚類質(zhì)量判定原則”，即通過組內(nèi)元素之間距離和組件元素距離兩個方面來判定聚類效果優(yōu)劣。并依據(jù)此原則提出了多個判別函數(shù)：DB函數(shù)、DI函數(shù)和CH函數(shù)，本文選取公認(rèn)判定效果最佳的CH函數(shù)

(1)

如式(1)，k代表聚類類別數(shù)，n代表數(shù)據(jù)集元素個數(shù)

(2)

如式(2)，traceB等于組和組之間離差矩陣的跡，nj等于第j個組中存在的元素的數(shù)目，u為數(shù)據(jù)集所有元素的均值，uj是第j個組中所有元素的均值

(3)

如式(3)，traceW表示組內(nèi)元素之間的離差矩陣的跡，xi代表第i個組內(nèi)元素。一般來說，聚類效果優(yōu)秀代表的是組與組之間的距離大，而組內(nèi)的元素距離小。也就是說，聚類質(zhì)量越好，CH值越大。

2.2.2 數(shù)據(jù)劃分流程

在機(jī)器學(xué)習(xí)索引模型中使用birch聚類算法進(jìn)行數(shù)據(jù)劃分可以根據(jù)數(shù)據(jù)集分布情況生成內(nèi)部分布更加統(tǒng)一的不同數(shù)據(jù)區(qū)域，進(jìn)而提升模型預(yù)測精度。

ULIB數(shù)據(jù)劃分流程如圖4所示，選擇數(shù)據(jù)開始訓(xùn)練過程后，讀入數(shù)據(jù)樣本，使用默認(rèn)B、L值進(jìn)行birch聚類，進(jìn)行閾值判定后更新CFtree，之后依次輸入不同的B、L值組合，CFtree在不斷地迭代中進(jìn)行更新，直至算法收斂結(jié)束聚類并記錄對應(yīng)CH值用于后續(xù)對比。

圖4 基于birch的數(shù)據(jù)劃分流程

2.3 葉子節(jié)點(diǎn)訓(xùn)練

2.3.1 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

ULIB設(shè)計的子模型神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示。

圖5 神經(jīng)網(wǎng)絡(luò)設(shè)置

具體訓(xùn)練流程為：

每個模型接收數(shù)據(jù)對應(yīng)類別列向量輸入X=[x1，x2，…，xd]T通過式(4)產(chǎn)生凈輸出a[1]，其中b為偏置，行向量W[1]為權(quán)重向量

a[1]=W[1]X+b

(4)

凈輸入a[1]通過Relu激活函數(shù)做實(shí)現(xiàn)非線性變換，如式(5)。得到輸入為X時該神經(jīng)元的活性值a[2]

a[2]=ρ(a[1])=max(a[1]，0)

(5)

如式(6)所示，輸出預(yù)測值y

y=ρ(W[2]a[2]+b2)

(6)

2.3.2 子模型設(shè)置及損失函數(shù)優(yōu)化

ULIB其中一個子模型k訓(xùn)練過程如圖6所示，在訓(xùn)練階段，ULIB會根據(jù)birch聚類階段產(chǎn)生的k個數(shù)據(jù)區(qū)域分別構(gòu)造k個模型，其中各個模型為兩層神經(jīng)網(wǎng)絡(luò)，輸入為待檢索數(shù)據(jù)的鍵，輸出為預(yù)測的位置，使用神經(jīng)網(wǎng)絡(luò)進(jìn)行葉子節(jié)點(diǎn)訓(xùn)練可以適應(yīng)各種場景下的非線性擬合需求，提升預(yù)測精度。

圖6 子模型結(jié)構(gòu)

為了實(shí)現(xiàn)進(jìn)一步提升模型性能，將數(shù)據(jù)訪問熱度融入到損失函數(shù)構(gòu)造中，即針對熱點(diǎn)訪問的數(shù)據(jù)，模型訓(xùn)練過程中會增加其權(quán)重，宏觀上彌補(bǔ)了緩沖區(qū)帶來的性能損耗。

更新?lián)p失函數(shù)如式(7)，其中，x為輸入數(shù)據(jù)的主鍵，y為輸入數(shù)據(jù)項(xiàng)對應(yīng)的位置，f1(x)到fk(x)代表第1個到第k個訓(xùn)練模型，λx代表數(shù)據(jù)項(xiàng)x的訪問熱度信息，這個值由實(shí)際生活中對于x的訪問次數(shù)決定，針對不同的數(shù)據(jù)項(xiàng)i會有不同的λx值。優(yōu)化目標(biāo)是最小化損失函數(shù)

(7)

2.4 基于LSM的索引更新

模型訓(xùn)練得出的數(shù)據(jù)區(qū)域設(shè)為D1到Dk，訓(xùn)練模型fi(x)對應(yīng)的數(shù)據(jù)區(qū)域是Di。當(dāng)一個待檢索數(shù)據(jù)x輸入后，輸出的y就是模型計算出的x對應(yīng)的數(shù)據(jù)區(qū)域Di中的預(yù)測的位置。計算x對應(yīng)的存儲真實(shí)位置是D1到Di-1的所有數(shù)據(jù)區(qū)域的數(shù)據(jù)量的累計值加上預(yù)測位置y，也就是說，只需要記錄下各個數(shù)據(jù)區(qū)域的數(shù)據(jù)量，即可通過計算確定x對應(yīng)的訓(xùn)練模型，而且插入操作完成后，只對x對應(yīng)的數(shù)據(jù)區(qū)域Di中的數(shù)據(jù)量和數(shù)據(jù)分布產(chǎn)生影響，訓(xùn)練時也只需要重新訓(xùn)練Di，其它數(shù)據(jù)區(qū)域不需要進(jìn)行重訓(xùn)練，依舊可以通過對應(yīng)的f(x)計算出待檢索鍵的相對位置y，之后累加位于這個數(shù)據(jù)區(qū)域之前的所有數(shù)據(jù)區(qū)域數(shù)據(jù)累計量的大小得到待檢索鍵的真正的位置，模型間實(shí)現(xiàn)了互不干擾。

但是當(dāng)插入條目較多時，每次插入都要對對應(yīng)數(shù)據(jù)區(qū)域進(jìn)行重訓(xùn)練依然會給模型帶來不小的開銷，進(jìn)而影響模型性能。基于日志結(jié)構(gòu)的LSM樹，是一種寫優(yōu)化的數(shù)據(jù)組織方式，其核心思想包括延遲更新，核心為延遲批處理索引變更請求，采用類似歸并排序的方式串聯(lián)所有的變更信息，最后統(tǒng)一將變更遷移至磁盤[16]。

為此，如圖7所示，模型借鑒了LSM樹的延遲更新思路。在插入過程開始后，首先在內(nèi)存中劃分一塊新的緩存，并將其分為k個緩存塊，分別對應(yīng)k個數(shù)據(jù)區(qū)域。當(dāng)一條待插入數(shù)據(jù)請求生成后，模型首先根據(jù)待插入數(shù)據(jù)的輸入值x計算確定其對應(yīng)存儲數(shù)據(jù)區(qū)域Di，然后將這條數(shù)據(jù)存儲到被劃分號的第i個緩存塊中以B樹形式存儲，只有當(dāng)這個緩存塊達(dá)到閾值溢出以后，才將其中的數(shù)據(jù)歸并到實(shí)際的數(shù)據(jù)區(qū)域，并重新訓(xùn)練。至此完成一次插入操作。使用這樣的異地插入不僅能夠分?jǐn)倲?shù)據(jù)移位代價，還能分?jǐn)偰Ｐ椭赜?xùn)練代價。

圖7 索引更新

2.5 數(shù)據(jù)檢索過程

當(dāng)各個神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練完成以后，都會相應(yīng)生成一個適配各個模型的最大檢索誤差值。而且每一個模型對應(yīng)的數(shù)據(jù)區(qū)域都存在一個存儲范圍，這個范圍決定了檢索時待檢索鍵對應(yīng)哪個模型。

在檢索階段，模型首先根據(jù)輸入的待檢索鍵x的大小來確定其范圍，進(jìn)而根據(jù)范圍確定x對應(yīng)的索引模型fi(x)，首先在fi(x)對應(yīng)的劃分緩沖區(qū)中第i個緩存塊中進(jìn)行查找，檢查x是否作為臨時數(shù)據(jù)存放在內(nèi)存中，若不在，則根據(jù)fi(x)計算出x在這個模型中存儲的預(yù)測位置y，并根據(jù)生成的error序列找到對應(yīng)的最大誤差，最后通過二分查找算法在預(yù)測位置y的最大誤差區(qū)間內(nèi)查找精確位置，完成檢索操作。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及設(shè)置

實(shí)驗(yàn)使用數(shù)據(jù)集為亞馬遜書籍排名數(shù)據(jù)集和Weblogs數(shù)據(jù)集，以連續(xù)取樣的方式各采樣了約300萬條不重復(fù)的數(shù)據(jù)。其中：書籍排名數(shù)據(jù)集是來自亞馬遜發(fā)布的書籍各個時間段銷售排名情況；weblog數(shù)據(jù)集采集了服務(wù)器端訪問日志記錄。兩個數(shù)據(jù)集都選擇時間戳作為訓(xùn)練用主鍵。

本文的實(shí)驗(yàn)硬件環(huán)境為：CPU為2.7 GHz的6核，內(nèi)存為60 G；硬盤容量為1 TB。訓(xùn)練使用的為一塊8 G GTX 1080 GPU。軟件環(huán)境：使用操作系統(tǒng)為 Windows10 x64；Python版本為Python 3.6；基于版本號為1.13.2的 TensorFlow實(shí)現(xiàn)機(jī)器學(xué)習(xí)部分。

實(shí)驗(yàn)對比模型設(shè)置：

ULIB：設(shè)置為兩層架構(gòu)，模型輸入為待檢索數(shù)據(jù)的鍵，輸出為鍵所預(yù)測的位置，隱藏層神經(jīng)元設(shè)置為32個，激活函數(shù)為Relu；

learned index：設(shè)置為兩層的遞歸回歸模型RMI，第一層使用神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，隱藏層設(shè)置為16*16個神經(jīng)元，激活函數(shù)為ReLu。輸出層設(shè)置為100個線性回歸模型；

B+樹：設(shè)置頁面大小為256，緩存為64 K；

ALEX：使用自適應(yīng)RMI模型，并在各個葉子節(jié)點(diǎn)加入空隙數(shù)組，大小為4倍鍵值數(shù)目。

3.2 聚類有效性評估指標(biāo)

本文使用了CH函數(shù)量化指標(biāo)來確定分支因子B和最大樣本半徑閾值T，為此，實(shí)驗(yàn)設(shè)計了不同分支因子B和不同最大樣本半徑閾值T來進(jìn)行組合實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表1、表2。

表1 不同T、B對應(yīng)CH指數(shù)(amon)

表2 不同T、B對應(yīng)CH指數(shù)(weblogs)

從結(jié)果可以看出，關(guān)鍵參數(shù)T/B分別為0.5/100和2/25時，CH函數(shù)值取最大，即此時聚類效果最好，后續(xù)實(shí)驗(yàn)均采用對應(yīng)參數(shù)。也就是說，針對不同的數(shù)據(jù)集，存在不同的最優(yōu)關(guān)鍵參數(shù)對來使模型分類效果獲得最優(yōu)。

3.3 模型性能對比分析

3.3.1 檢索性能對比

為了驗(yàn)證模型檢索性能優(yōu)勢，實(shí)驗(yàn)對比了ULIB、lear-ned index、B+樹和ALEX的檢索性能，如圖8、圖9所示。

圖8 檢索性能對比(amon)

其中橫軸代表生成的檢索負(fù)載，縱軸代表所需要的時間，其值越小，代表模型檢索吞吐量越大，即檢索性能越好。

結(jié)果表明，隨著檢索負(fù)載提高，檢索時間會正比增加，原因在于，神經(jīng)網(wǎng)絡(luò)中的矩陣運(yùn)算決定了檢索所需要的時間，而該過程與檢索負(fù)載成正比關(guān)系。

且ULIB在兩個數(shù)據(jù)集上檢索性能相比較B+樹、lear-ned index和ALEX也具有一定優(yōu)勢。原因在于ULIB模型在數(shù)據(jù)劃分階段使用birch聚類算法進(jìn)行劃分，各個數(shù)據(jù)區(qū)域內(nèi)分布更加趨于一致，從而使神經(jīng)網(wǎng)絡(luò)訓(xùn)練擬合度更高。另外，learned index使用的是多層遞歸RMI，而ULIB使用了兩層的非RMI設(shè)計，并且只在第二層輸出層使用神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練預(yù)測，因此在各個階段體現(xiàn)得更加輕量有效。

3.3.2 訓(xùn)練時間對比

為了測試ULIB訓(xùn)練時間，即模型建立所需時間，實(shí)驗(yàn)比較了ALEX、learned index和ULIB在相同數(shù)據(jù)集下模型建立完成所用時間，在兩個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果如圖10所示。

圖10 訓(xùn)練時間對比

結(jié)果表明，經(jīng)過birch聚類后的ULIB模型相比較learned index在兩個數(shù)據(jù)集的訓(xùn)練時間上存在明顯優(yōu)勢，主要原因是：在經(jīng)過聚類將數(shù)據(jù)集分類k類后，訓(xùn)練數(shù)據(jù)集變成了k個規(guī)模更小的數(shù)據(jù)區(qū)域，而機(jī)器學(xué)習(xí)訓(xùn)練時間隨數(shù)據(jù)規(guī)模增長可能是指數(shù)級增長的，所以相比較learned index直接訓(xùn)練所有數(shù)據(jù)而言，ULIB模型訓(xùn)練上會存在優(yōu)勢。

3.3.3 插入性能對比

為了驗(yàn)證ULIB在插入性能上的優(yōu)勢，實(shí)驗(yàn)比較了ULIB、B+樹和ALEX的插入性能對比。

實(shí)驗(yàn)結(jié)果如圖11、圖12所示，圖示分別代表在亞馬遜數(shù)據(jù)排名數(shù)據(jù)集和weblogs上實(shí)驗(yàn)結(jié)果，橫軸是待插入數(shù)據(jù)的數(shù)目，縱軸為完成插入操作所使用的時間。實(shí)驗(yàn)分別測試了2萬～10萬條插入請求時結(jié)果。

圖11 插入性能對比(amon)

圖12 插入性能對比(weblogs)

結(jié)果表明，ULIB在數(shù)據(jù)插入性能上，保持了對B+樹和ALEX的優(yōu)勢。原因在于，ULIB借鑒LSM樹中延遲更新思路在內(nèi)存中設(shè)置了緩存區(qū)，當(dāng)插入請求生成后，模型先將其插入至緩存塊中，只有內(nèi)存的緩存區(qū)占用達(dá)到閾值并溢出后，才轉(zhuǎn)移至對應(yīng)的數(shù)據(jù)區(qū)域，此時才對相對應(yīng)的數(shù)據(jù)區(qū)域進(jìn)行重訓(xùn)練，也正是因?yàn)檫@種機(jī)制，不會每次插入數(shù)據(jù)都需要對神經(jīng)網(wǎng)絡(luò)模型進(jìn)行重訓(xùn)練，實(shí)現(xiàn)了插入性能的優(yōu)化。

3.3.4 內(nèi)存占用對比

本節(jié)對比了3個模型在亞馬遜數(shù)據(jù)排名數(shù)據(jù)集上的內(nèi)存占用，結(jié)果見表3，其中15.7 M、213 M代表learned index和B+樹存儲實(shí)驗(yàn)數(shù)據(jù)所占用的空間，而60 K、180 K和890 K代表了各個機(jī)器學(xué)習(xí)索引中所設(shè)置的神經(jīng)網(wǎng)絡(luò)占用的空間。

表3 3種模型內(nèi)存占用對比

結(jié)果表明，B+樹在相同數(shù)據(jù)集下內(nèi)存占用最多。原因是B+樹中消耗了大量空間來存儲數(shù)據(jù)鍵和指針信息等額外數(shù)據(jù)，所以說，存儲的數(shù)據(jù)集越大，B+樹所需要的內(nèi)存就越大。而機(jī)器學(xué)習(xí)索引結(jié)構(gòu)只需要存儲神經(jīng)網(wǎng)絡(luò)模型參數(shù)和數(shù)據(jù)鍵，并不需要其它額外的空間，因此內(nèi)存占用情況相比較B+樹具有明顯優(yōu)勢。

另外，ULIB模型相比較而言更為輕量簡單，因此比learned index在內(nèi)存占用方面更具有優(yōu)勢。不過在參數(shù)B和T減小時，聚類類別數(shù)增加，神經(jīng)網(wǎng)絡(luò)內(nèi)存占用也會增加。

4 結(jié)束語

本文確立了學(xué)習(xí)化索引結(jié)構(gòu)實(shí)現(xiàn)的關(guān)鍵要素，提出可更新機(jī)器學(xué)習(xí)索引檢索模型ULIB，最后在亞馬遜書籍排名和weblogs數(shù)據(jù)集上分別進(jìn)行測試實(shí)驗(yàn)。經(jīng)實(shí)驗(yàn)驗(yàn)證，結(jié)論如下：①采用birch聚類進(jìn)行數(shù)據(jù)劃分時，CH函數(shù)作為參考依據(jù)來可以找到關(guān)鍵參數(shù)B和T的局部最優(yōu)解；②相比較learned index、ALEX和B+樹索引結(jié)構(gòu)，ULIB在相同數(shù)量級上檢索性能、訓(xùn)練時間、插入性能和內(nèi)存占用均有更好的表現(xiàn)。

下一步研究工作在于，目前B和T的取值是通過在實(shí)驗(yàn)中進(jìn)行調(diào)整，從而實(shí)現(xiàn)局部最優(yōu)，可以嘗試從數(shù)學(xué)角度計算推導(dǎo)全局最優(yōu)解。