關(guān)系數(shù)據(jù)庫帝國已經(jīng)獨孤求敗幾十年了!
自從1970年E.F.Codd 的《大型共享數(shù)據(jù)庫的關(guān)系模型》論文橫空出世，為關(guān)系型數(shù)據(jù)庫奠定了堅實的理論基礎(chǔ)振愿，一眾關(guān)系數(shù)據(jù)庫System R，DB2 ，Oracle，MySQL赎离，Postgres相繼誕生，一舉推翻了層次和網(wǎng)狀數(shù)據(jù)庫的統(tǒng)治端辱。
在過去的幾十年中梁剔， 對象數(shù)據(jù)庫， NoSQL等相繼挑戰(zhàn)舞蔽，但是依然無法撼動它的地位荣病。
當(dāng)然關(guān)系數(shù)據(jù)庫也不是停滯不前，它也在進化渗柿，統(tǒng)一的SQL標準个盆，強大的事務(wù)支持，更加聰明的查詢優(yōu)化器......
但是帝國也有一個巨大的硬傷，數(shù)據(jù)都保存在硬盤上砾省，比起內(nèi)存和CPU來鸡岗，硬盤實在是太慢了。 如果說內(nèi)存是火箭的話编兄，硬盤就是驢車。
帝國想出了很多辦法声登，但總是不能徹底解決問題狠鸳，到目前為止，一個比較好的辦法就是使用B+樹悯嗓。
比如有一張表User, 假設(shè)它只有兩列(id, age)件舵，ID為主鍵Key。
圖1
那么它的B+樹存儲結(jié)構(gòu)為：
(圖2：B+樹中節(jié)點也保存在磁盤塊中)
最后一層為有序的數(shù)據(jù)頁脯厨，每個頁包含指向下一個數(shù)據(jù)頁的頁號(也就是地址)铅祸，這里假設(shè)一條記錄占據(jù)一個數(shù)據(jù)頁,那么第一條記錄在1號數(shù)據(jù)頁，第二條記錄在2號數(shù)據(jù)頁合武，依次類推临梗。
這樣以來，如果用戶想獲取ID = 4的記錄稼跳，數(shù)據(jù)庫只需要讀取三次磁盤就可以找到記錄所在的數(shù)據(jù)的頁號(page)為4盟庞。
圖3
機器學(xué)習(xí)大使
這一天， 帝國的早朝上來了一位神秘的客人汤善，號稱是機器學(xué)習(xí)王國的大使什猖，他自稱帶來了一個咒語，能夠根據(jù)一個數(shù)據(jù)庫記錄的索引列的值(比如主鍵Key=4)红淡，瞬間定位到記錄的頁號( page = 4)不狮，連那三次硬盤讀寫都不需要。
這絕對是個革命性的技術(shù)在旱，國王非常感興趣摇零，下旨讓大使詳細講述。
B+樹大臣馬上就感受到了威脅颈渊，如果真有這個咒語遂黍，自己官位不保，于是他趕緊阻止：“陛下俊嗽，老夫有所耳聞雾家，機器學(xué)習(xí)雖然風(fēng)靡IT世界，但是也有很多招搖撞騙绍豁，不著邊際的故事芯咧，這個大使，很有可能就是想推銷幾個鬼都看不懂的數(shù)學(xué)模型來騙錢!”
國王把沒有說話，把目光射向大使敬飒。
機器學(xué)習(xí)大使臉微微一沉邪铲，心中想到，不把這個老頭子搞定无拗，也就無法說服國王带到， 既然你送上門來，我就拿你開刀吧英染。
他主意打定揽惹，胸有成竹，先給B+樹大臣戴高帽挖個坑： “大人誤會了四康，小人知道您在數(shù)據(jù)庫王國是絕對的中流砥柱搪搏， 您采用多叉平衡樹的方式，降低了索引層次闪金，減少了硬盤I/O時間疯溺，并在葉子節(jié)點上維護一個根據(jù)key(索引列)排序的線性表(S)，獲得了范圍查詢的能力....”
B+樹微微一笑哎垦，心想這小子是有備而來啊囱嫩，懂得不少。
從key直接找到page
然而大使話鋒一變：“但是撼泛，說白了挠说，它就是一個通過key獲取數(shù)據(jù)記錄頁面(page)一個映射關(guān)系!而這和機器學(xué)習(xí)中的回歸要干的事情是一樣的，都是通過一些特征預(yù)測目標值愿题，比如通過每個人的年齡损俭，收入等信息預(yù)測你的潛力值，只不過說在數(shù)據(jù)庫這個場景下key是特征潘酗，page是目標值杆兵。”
B+樹不屑道：“難道機器學(xué)習(xí)只要是映射就可以學(xué)嗎?有點忽悠了吧!”
大使忍住這當(dāng)面的嘲諷仔夺，平心靜氣地說：“您要知道琐脏，這個key和page之間是有關(guān)系的!而您正是忽略它兩者可能存在的強關(guān)聯(lián)!「淄茫”
說到這里日裙，大使不知道從哪里變出一塊小黑板，在上面畫了圖2惰蜜，然后說：“比如說我現(xiàn)在有一堆數(shù)據(jù)昂拂，每條記錄占一個數(shù)據(jù)頁，他們的key和page之間的關(guān)系是這樣的 ”
機器學(xué)習(xí)大使清了清嗓子：“對于機器學(xué)習(xí)模型抛猖，比如我用一個簡單的線性回歸算法格侯，假定模型為page=a * key + b鼻听，而我們當(dāng)前訓(xùn)練集，也就是這棵B+樹中key與之對應(yīng)page數(shù)據(jù)(1,1),(2,2)…(12,12)联四，也就是說a,b必須得滿足1=a+b,2=2a+b…12=12a+b這12個等式撑碴，就相當(dāng)于我們小時候求解二元一次方程組一般，我們得到a = 1,b = 0, 于是乎我們得到了最終模型page = key!”
應(yīng)對復(fù)雜情況
B+樹大臣冷笑一聲朝墩，轉(zhuǎn)向國王：“陛下醉拓，別被他的數(shù)學(xué)公式蒙蔽，這是騙小孩的把戲!哪有page = key這么簡單的情況! 再說了收苏，這種簡單的情況廉嚼，還用得著機器學(xué)習(xí)? 我用肉眼都看出來他們的關(guān)系是page=key! 來來來，機器學(xué)習(xí)大使倒戏，我給你說個復(fù)雜點兒的情況，如果有些數(shù)據(jù)頁能裝兩條記錄呢?你給我說說page 和key 之間的關(guān)系是啥?”
現(xiàn)在的對應(yīng)關(guān)系不是那么簡單了恐似。
機器學(xué)習(xí)大使不僅不慢不緊不慢地回答道：“線性模型只是我們大家族中最簡單的地模型罷了杜跷，不管你一個數(shù)據(jù)頁能存儲幾條記錄， 只要給出(key,page)對應(yīng)的數(shù)據(jù)集合,我們都可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)矫夷，找到滿足他們之間關(guān)系的一個函數(shù) page = f(key)!通過這個函數(shù)葛闷，只要你給出key的值，立刻就能得出page! ”
B+樹有點明白了双藕，這機器學(xué)習(xí)就是為了找到一個key和頁面之間的關(guān)系啊淑趾，以后訪問起來就方便了，他背上開始冒汗了忧陪。
機器學(xué)習(xí)大使窮追不舍扣泊，亮出了最大殺招：“使用B+樹， 存儲開銷是O(n/m)(m為樹的出度)嘶摊，查詢開銷是O(log(n))延蟹， 而使用神經(jīng)網(wǎng)絡(luò)，查詢開銷是O(1) !”
O(1) !
聽到這句話叶堆， 全場一片嘩然阱飘，所有人都知道這意味著什么，這就是革命呀虱颗，革B+樹的命呀!
大臣們開始竊竊私語：“這神經(jīng)網(wǎng)絡(luò)很厲害啊!”
“是啊!神經(jīng)網(wǎng)絡(luò)最擅長干這個事情了!從一堆數(shù)據(jù)中找到關(guān)聯(lián)關(guān)系沥匈。”
“聽說神經(jīng)網(wǎng)絡(luò)在兩層的情況下就能夠擬合一切函數(shù)!”
B+樹大臣有點慌忘渔，語氣也弱了下來：“你們機器學(xué)習(xí)是很牛逼高帖，但像LR，GBDT辨萍，SVR棋恼，包括你說的這些神經(jīng)網(wǎng)絡(luò)返弹，一些深度學(xué)習(xí)的方法，哪個不是有一定錯誤率的爪飘，位置預(yù)測錯誤义起，難道要全部掃描一遍數(shù)據(jù)不成，你們懂不懂我們索引的業(yè)務(wù)呀!”
機器學(xué)習(xí)大使早就預(yù)料到了會有這個問題师崎， 他一字一句鄭重道：“將機器學(xué)習(xí)賦能數(shù)據(jù)庫默终，我們是認真的! 傳統(tǒng)這些預(yù)測算法的應(yīng)用場景，都是在訓(xùn)練數(shù)據(jù)數(shù)據(jù)集里做訓(xùn)練犁罩，然后對未知的數(shù)據(jù)做預(yù)測齐蔽。但索引這個場景，嘿嘿床估，它是一個封閉場景含滴，沒有新的數(shù)據(jù)，只需要對數(shù)據(jù)庫中存在的數(shù)據(jù)做預(yù)測即可丐巫，這種場景下谈况，就像我剛才提到的神經(jīng)網(wǎng)絡(luò)完全可以勝任，直接就在當(dāng)前數(shù)據(jù)上递胧，訓(xùn)練到做到百分百的正確率即可碑韵。”
全場再次嘩然缎脾，眾位大臣齊刷刷地看著國王祝闻，似乎等待著最終的宣判。
絕地反擊
B+樹大臣頓時印堂發(fā)黑遗菠，心想幾十年的風(fēng)光就要今日終結(jié)嗎联喘，本來隨著SSD等新型硬件的誕生我的日子就不好過了， 難道今日命喪機器學(xué)習(xí)之手?悲傷難以平復(fù)舷蒲，搖搖欲墜耸袜。
這個時候，CBO(基于代價的優(yōu)化器)從后面走過來牲平，一把扶住B+樹堤框，看著這個日益蒼老的老頭，說道：“大人莫慌纵柿，別看他和囂張蜈抓，但是有巨大漏洞，看我來對付他昂儒」凳梗”
CBO大臣說道：“你之前說的只是查找和存儲性能，索引的維護(增/刪/改)代價難道不用考慮嗎渊跋，如果索引發(fā)生了變化腊嗡，之前的page= f(key)這個函數(shù)還有效嗎? 是不是還得重新訓(xùn)練神經(jīng)網(wǎng)絡(luò)着倾，找到新的函數(shù) page = f1(key)? 這還是O(1)的時間復(fù)雜度嗎?我們數(shù)據(jù)庫面對的是通用場景，不要以為只考慮幾個case就覺得可以替代我們了!”
機器學(xué)習(xí)大使大驚燕少，功敗垂成!自己已經(jīng)隱藏的這么深卡者，還是被發(fā)現(xiàn)了缺陷，頓時紅了個臉：“您說的對客们，我們在索引的更新上還沒有很好的解決方案崇决，但我們只是想為數(shù)據(jù)庫索引帶來一些新鮮想法，做現(xiàn)在的技術(shù)選項的補充底挫，并沒有想著取代誰恒傻。”
B+樹一聽建邓，立刻滿血復(fù)活：“陛下盈厘，您看看，這是一個不成熟的方案官边，對于數(shù)據(jù)查找能做到O(1)扑庞， 但是對于數(shù)據(jù)更新就完全不行了，居然還想替代我!我就說這機器學(xué)習(xí)是招搖撞騙嘛!”
數(shù)據(jù)庫國王搖搖頭：“愛卿所言差矣拒逮，這個機器學(xué)習(xí)的思路還是非常新奇的，我們還是要學(xué)習(xí)一下的臀规， 來人滩援，給機器學(xué)習(xí)大使送上白銀千兩，好好安頓塔嬉⊥婊玻”
后記
這篇文章的靈感來源于一篇論文《The Case for Learned Index Structures》，實際上真正要把機器學(xué)習(xí)應(yīng)用的索引上谨究，就算考慮只讀場景恩袱，往往也會因為數(shù)量太大，關(guān)系太多復(fù)雜胶哲，導(dǎo)致計算量畔塔、模型復(fù)雜度方面的問題，所以提出這個論文的作者提到通過建立層次模型的方式解決：根節(jié)點的分類器將記錄劃分成n份鸯屿，給下一層分類器進行分類澈吨，這樣節(jié)點的預(yù)測器學(xué)習(xí)的數(shù)據(jù)少而簡單，總體的時間成本也能夠保證寄摆。
