??上篇文章簡單的填了一個(gè)坑基于LSM數(shù)據(jù)庫的實(shí)現(xiàn)了WAL，在該版本中如數(shù)據(jù)寫入到內(nèi)存表的同時(shí)將未持久化的數(shù)據(jù)寫入到WAL文件，在未將數(shù)據(jù)持久化時(shí)程序崩潰，可通過WAL文件將數(shù)據(jù)還原恢復(fù)從而避免了數(shù)據(jù)的丟失。
目前此基于LSM的數(shù)據(jù)庫還有三大坑：
?? 1、索引問題
?? 2、SSTable合并問題
?? 3、單機(jī)版本問題；
??本篇文章將解決其中的一個(gè)坑，索引問題；

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了赫章免費(fèi)建站歡迎大家使用！

索引問題

??到目前為止還沒有詳細(xì)解釋當(dāng)前系統(tǒng)的索引問題到底是什么，不解決會(huì)導(dǎo)致什么問題；目前系統(tǒng)在寫入數(shù)據(jù)將數(shù)據(jù)持久化到SSTable文件并寫每一個(gè)SSTable文件對(duì)應(yīng)的索引數(shù)據(jù)時(shí)是為每個(gè)數(shù)據(jù)項(xiàng)Key都記錄了相應(yīng)的索引數(shù)據(jù)，此時(shí)的索引為全量索引；
??全量索引就會(huì)導(dǎo)致索引文件快速增大，索引文件過大后維護(hù)的性能、查詢性能就會(huì)大幅下降；索引此時(shí)需要解決索引文件快速增大問題；這里引入了：稀疏索引，稀疏索引也是業(yè)內(nèi)比較常見，普遍用到的數(shù)據(jù)結(jié)構(gòu)；下面詳細(xì)介紹對(duì)比全量索引與稀疏索引的區(qū)別；

??全量索引樹為每個(gè)key存儲(chǔ)對(duì)應(yīng)的key在數(shù)據(jù)文件中的起始位置、數(shù)據(jù)項(xiàng)長度，導(dǎo)致其索引結(jié)構(gòu)無比龐大；

??經(jīng)過優(yōu)化，此稀疏索引樹結(jié)構(gòu)每隔指定間隔才存儲(chǔ)一個(gè)索引項(xiàng)；
??存儲(chǔ)的數(shù)據(jù)為每個(gè)間隔區(qū)間的所有key數(shù)據(jù)，Key為該批的第一個(gè)key，值為此批次的：起始位置、批次數(shù)據(jù)項(xiàng)長度，使得索引結(jié)構(gòu)容量大大減少；
??本圖為間隔兩個(gè)Key存儲(chǔ)一個(gè)索引；

??節(jié)點(diǎn)AAA： 存儲(chǔ)AAA、CCC數(shù)據(jù)索引
??節(jié)點(diǎn)DDD： 存儲(chǔ)DDD、EEE數(shù)據(jù)索引
??節(jié)點(diǎn)HHH： 存儲(chǔ)HHH數(shù)據(jù)索引
??節(jié)點(diǎn)FFF： 存儲(chǔ)FFF、GGG數(shù)據(jù)索引

索引查詢

??此時(shí)稀疏索引的存儲(chǔ)結(jié)構(gòu)方式已經(jīng)解決，在查詢與之前也有不少區(qū)別；
??全量索引：使用key在索引樹查找對(duì)應(yīng)數(shù)據(jù)項(xiàng)，根據(jù)索引存儲(chǔ)的start、length去對(duì)應(yīng)的數(shù)據(jù)文件讀取相應(yīng)的數(shù)據(jù)；
??稀疏索引：在索引樹中查找最后一個(gè)小于所查詢key的key節(jié)點(diǎn)、第一個(gè)大于所查詢key的key節(jié)點(diǎn)，使用該節(jié)點(diǎn)存儲(chǔ)的start、length去對(duì)應(yīng)數(shù)據(jù)文件讀取相應(yīng)的數(shù)據(jù)塊，從中對(duì)比查找出所查詢的key；

??經(jīng)過此次索引結(jié)構(gòu)的優(yōu)化，又填了一大坑，還有兩大坑待解決：
??1、SSTable合并問題
??2、單機(jī)版本問題；

文章首發(fā)地址：https://mp.weixin.qq.com/s/YyXoePq7FamfnfRg0K6-yA

新聞標(biāo)題：基于LSM的Key-Value數(shù)據(jù)庫實(shí)現(xiàn)稀疏索引篇
網(wǎng)頁URL：http://chinadenli.net/article10/dsoisgo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站制作、全網(wǎng)營銷推廣、虛擬主機(jī)、外貿(mào)網(wǎng)站建設(shè)、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)