今天終於要來看測試結果ㄌ，Kraska et al.使用生活中實際、綜合的數據集比較Learned Index與傳統索引的查詢時間、空間利用率。

Integer Datasets

測試資料集有以下三種 :

• Weblogs
  • 200M筆資料
  • timestamps為Key值
  • 資料所呈現的分布相較複雜
• Maps [1]
  • 200M筆資料
  • 某些建築物(e.g., 道路、博物館、咖啡廳)的座標為資料
  • 經度為Key值
  • 資料的分布較線性
• Lognormal
  • 190M筆資料
  • 以 mean=0, sigma=2產生指數正常分布的資料
  • 分布較極端，資料集中在尾巴

Index Structures

我們比較的索引結構為 Learned Index 與 B+-Tree，下面為各結構的配置 :

• Learned Index
  • 2層結構，第一層1個Model，第二層配置不同數量的Models(10k, 50k, 100k, 200k)
  • 經由他們測試發現，第一層的Model使用 0 hidden layers (Simple Linear Regression) ~ 2 hidden layers(神經元數量為 8 or 16)最佳。第二層Models則是使用 Simple Linear Regression 最佳。
• B+-Tree
  • 使用高度優化的 B+-Tree 類似 stx::btree
  • page-size(這裡是指 node-size)的配置有 32, 64, 128 ,256, 512

Learned Index vs B-Tree performance

這裡說明一下上面標題的 B-Tree 是指 B+-Tree 呦 (在這篇Paper都是以B-Tree表示，不知為何??)

Model為執行索引的時間，Lookup為最後進行查找(Binary Search)的時間。

B-Tree 在 page size=128 時有最佳的效能，為標註灰色的部分，空間與查詢效能上都兼顧。

然而，Learned Index 不論是在空間或是查找時間上都比BTree好太多了 !

Learned Index 的查找速度比 B-Tree 快 1.5 - 3倍，空間利用率則是將近小了 2倍，完勝!

今天先到這嘞 ~

明天我們會繼續講剩餘的測試結果，掰噗 !

References

[1] OpenStreetMap database ©OpenStreetMap contributors. https://aws. amazon.com/public-datasets/osm.