一冈欢、典型的3種存儲(chǔ)引擎

1、hash：

代表：nosql的redis/memcached

本質(zhì)為： 基于(內(nèi)存中)的hash盈简；

所以支持 隨機(jī) 的增刪查改，讀寫的時(shí)間復(fù)雜度O(1)；

但是無法支持順序讀寫(注柠贤，這里指典型的hash香浩，不是指如redis的基于跳表的zset的其他功能)；

基本效果：在不需要有序遍歷時(shí)臼勉，最優(yōu)

2邻吭、磁盤查找樹：

代表：mysql

本質(zhì)為：基于(磁盤的)順序查找樹，B樹/B+樹宴霸；

基本效果：支持有序遍歷囱晴；但數(shù)據(jù)量很大后，隨機(jī)讀寫效率低(原因往下看)瓢谢；

3畸写、lsmtree：

代表：leveldb/rocksdb

本質(zhì)為： 實(shí)際落地存儲(chǔ)的數(shù)據(jù)按key劃分，形成有序的不同的文件氓扛；

結(jié)合其“先內(nèi)存更新后合并落盤”的機(jī)制枯芬，盡量達(dá)到磁盤的寫是順序?qū)懀M可能減少隨機(jī)寫采郎；

對(duì)于讀千所，需合并磁盤已有歷史數(shù)據(jù)和當(dāng)前未落盤的駐于內(nèi)存的更新，較慢蒜埋；

基本效果：也可以支持有序增刪查改淫痰；寫速度大幅提高；讀速度稍慢整份；

重大改進(jìn)點(diǎn)：

寫：

1待错、將隨機(jī)的寫(的操作)保存于內(nèi)存中，達(dá)到一定量后皂林，寫磁盤朗鸠；而不是每次都去落盤；

2础倍、落盤的文件(即level0以下層的文件烛占，不含memtable即level0的文件)，不論文件內(nèi)部還是文件相互之間沟启，均按key有序忆家，可以二分查找，故無論是讀德迹，還是其合并操作芽卿，均為對(duì)數(shù)時(shí)間；

3胳搞、結(jié)合1和2卸例，盡可能的減少了隨機(jī)寫称杨；實(shí)現(xiàn)了有效的按順序讀寫；

4筷转、落盤的數(shù)據(jù)姑原，會(huì)定期進(jìn)行文件合并，即由多個(gè)小文件的二分查找合并為一個(gè)大文件呜舒，進(jìn)一步利于增刪查改效率锭汛；

讀：

lsmtree引擎的讀，需要在落盤文件中袭蝗，查找要查的所有key唤殴，并查看當(dāng)前未落盤的更新中是否存在相關(guān)的修改，較麻煩但也有優(yōu)化到腥；

二朵逝、數(shù)據(jù)和索引：

1、由key找value就是索引左电；

比如二叉查找樹廉侧、平衡二叉樹、紅黑樹篓足，每一個(gè)節(jié)點(diǎn)段誊，可以存儲(chǔ)數(shù)據(jù)，可以存儲(chǔ)數(shù)據(jù)所在地址栈拖，可以log(N)的找到增刪查改连舍，可以有序遍歷，到這就是索引涩哟；

比如一個(gè)有序數(shù)組索赏，每個(gè)數(shù)組元素，包括key和value贴彼，value來存儲(chǔ)數(shù)據(jù)潜腻，或者存儲(chǔ)數(shù)據(jù)地址，可以按key二分查找器仗；這也是索引融涣；

2、B樹和B+樹：

實(shí)際上沒有使用1中的二叉樹精钮、有序數(shù)組來存儲(chǔ)數(shù)據(jù)的威鹿；因?yàn)椋?/p>

1、數(shù)據(jù)量很大時(shí)轨香，二叉樹非常高忽你，需要很多步；

2臂容、有序數(shù)組如果隨機(jī)的插入刪除科雳，效果會(huì)如何根蟹；

B族樹最常用于數(shù)據(jù)庫如mysql的存儲(chǔ)引擎：

首先是B樹：

特征：

1、每個(gè)節(jié)點(diǎn)不再只有一個(gè)key炸渡，而是多個(gè)key娜亿；相比二叉樹，有效壓低了樹高

2蚌堵、和典型二叉樹一樣，依然是每個(gè)節(jié)點(diǎn)包括key和value沛婴；這加劇了隨機(jī)IO問題吼畏，也是B+樹被使用的原因；

典型B樹嘁灯，形似"多叉樹"泻蚊，且每個(gè)節(jié)點(diǎn)包括多個(gè)有序節(jié)點(diǎn)，其訪問方法丑婿，和二叉樹道理一樣性雄，只是每個(gè)樹的節(jié)點(diǎn)，包括了多個(gè)key而不是二叉樹那樣只有一個(gè)key羹奉，這樣樹的高度大大被壓低秒旋，以其查詢偽代碼為例加深印象：

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
            if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

如同AVL、紅黑樹一樣诀拭，增刪節(jié)點(diǎn)會(huì)導(dǎo)致B樹分裂迁筛；
其讀寫的算法訪問效率是對(duì)數(shù)級(jí)的，了解到這夠用耕挨。

實(shí)際的數(shù)據(jù)庫磁盤讀寫细卧，如果是B樹的話，會(huì)是這樣做：

1筒占、最開始創(chuàng)建B樹時(shí)：

磁盤中申請(qǐng)空間贪庙，載入到內(nèi)存，寫入翰苫；

2止邮、key按順序不斷寫入磁盤時(shí)：

順序?qū)懭氪疟P，速度非掣锕牵快农尖，如按順序insert大量數(shù)據(jù)到mysql時(shí)，因?yàn)椋?/p>

1良哲、每次都是申請(qǐng)一個(gè)磁盤頁(如4K大小)盛卡，而不是要寫幾個(gè)字節(jié)申請(qǐng)幾個(gè)字節(jié)；

2筑凫、B樹順序?qū)懙臅r(shí)候滑沧，數(shù)據(jù)都是向后自然順延并村，不發(fā)生分裂，除非當(dāng)前磁盤頁寫滿時(shí)滓技，再申請(qǐng)一個(gè)新的磁盤頁哩牍，繼續(xù)順序?qū)懀?/p>

3、當(dāng)B樹很大時(shí)令漂，隨機(jī)的寫時(shí)：

比如膝昆，刪除某一個(gè)key1，然后又更新一個(gè)key2的數(shù)據(jù)叠必，key1和key2不在同一個(gè)磁盤頁中荚孵，然后又增加一個(gè)key3導(dǎo)致發(fā)生分裂；

比如有大量的這樣的操作纬朝，導(dǎo)致：

1收叶、尋找key1時(shí)，內(nèi)存未找到共苛，被迫從磁盤里讀取一個(gè)頁判没；

2、刪除后可能導(dǎo)致B樹分裂隅茎，可能又導(dǎo)致更新磁盤里的其他數(shù)據(jù)澄峰；

3、增加一個(gè)key3患膛，又沒有找到摊阀，再次從磁盤讀取一個(gè)頁；可能導(dǎo)致分裂踪蹬，再次導(dǎo)致更新磁盤其他頁數(shù)據(jù)

4胞此、更新一個(gè)key2，又沒有找到跃捣；

5漱牵、最后會(huì)發(fā)現(xiàn)，數(shù)據(jù)越來越多后疚漆，增刪查改操作酣胀，到處都是磁盤IO，經(jīng)常需要從磁盤里讀娶聘，然后寫闻镶；

B+樹的改進(jìn)：

1、非葉子節(jié)點(diǎn)不再存儲(chǔ)數(shù)據(jù)丸升；好處是铆农，使每一個(gè)磁盤頁里，有更多一些的節(jié)點(diǎn)狡耻；能夠減少一些磁盤IO墩剖；

2猴凹、mysql實(shí)際使用時(shí)，葉子節(jié)點(diǎn)加入了相鄰葉子節(jié)點(diǎn)的指針岭皂；好處是郊霎，在有序遍歷時(shí)，找到了一個(gè)葉子爷绘，就可以順序的訪問其他葉子书劝，避免了都從根節(jié)點(diǎn)遍歷；又減少了一些磁盤IO揉阎；

B+樹庄撮，在非葉子層不再存儲(chǔ)數(shù)據(jù)，因而每個(gè)樹節(jié)點(diǎn)變小毙籽，也就集中了更多的節(jié)點(diǎn)；增多了一個(gè)磁盤頁中毡庆，實(shí)際節(jié)點(diǎn)的個(gè)數(shù)坑赡；這對(duì)于減少磁盤IO是有很大意義的；mysql就是使用B+樹作為數(shù)據(jù)索引么抗；

B+樹如下圖：

至此毅否，對(duì)基于B族樹的存儲(chǔ)引擎的mysql，其查詢效率就是：

1蝇刀、盡可能使按可以的順序?qū)懭耄?/p>

2螟加、在隨機(jī)不按key順序的增刪查改時(shí)，就沒辦法了吞琐，B+樹盡可能一個(gè)磁盤頁里有更多的節(jié)點(diǎn)捆探，減少磁盤IO次數(shù)，葉子節(jié)點(diǎn)中加入相鄰的指針站粟，進(jìn)一步減少磁盤IO黍图，更方便范圍檢索；

現(xiàn)在看一下奴烙，同樣基于B+樹的數(shù)據(jù)結(jié)構(gòu)助被，mysql兩種典型的索引方式的實(shí)現(xiàn)：

1、myisam：

myisam對(duì)于表的主鍵的索引方式切诀，如一個(gè)表有3個(gè)列揩环，col1、col2幅虑、col3

myisam的葉子存儲(chǔ)的數(shù)據(jù)是丰滑，數(shù)據(jù)所在的地址，而不是數(shù)據(jù)內(nèi)容

下圖是myisam的非主鍵的索引翘单，和主鍵索引方式差不多吨枉，也是存數(shù)據(jù)的地址：

myisam的索引方式的表蹦渣，在查詢時(shí)先通過B+樹找到key，進(jìn)而找到數(shù)據(jù)地址貌亭，然后再根據(jù)地址柬唯，找到數(shù)據(jù)內(nèi)容；

2圃庭、innodb：

再來看一下innodb的锄奢，使用過mysql的都知道如下準(zhǔn)則或建議：

1、innodb的表要求必須有主鍵剧腻；

2拘央、主鍵盡可能建議是，按順序自增的id书在；

3灰伟、主鍵不應(yīng)該太長(zhǎng)；

來看下為什么儒旬，下面是innodb的表的主鍵的索引：

innodb索引方式是把數(shù)據(jù)完全放在葉子節(jié)點(diǎn)上栏账，而不是myisam那樣只存數(shù)據(jù)地址；

再來看innodb的表的輔助鍵的索引：

看吧栈源，innodb的表的輔助鍵的索引挡爵，存的其實(shí)是它對(duì)應(yīng)的主鍵；

也就是：

1甚垦、innodb的索引茶鹃，其實(shí)都是到它的主鍵索引，比如通過輔助鍵的查詢艰亮，就是先通過輔助鍵索引闭翩，查到對(duì)應(yīng)的主鍵，然后再去查主鍵的索引垃杖；

這就是為什么男杈，innodb的表必須有主鍵；

同時(shí)也是為什么调俘，innodb的表的行鎖伶棒，其實(shí)也只是支持字段是主鍵時(shí)的操作時(shí)；如果是非主鍵字段彩库，和myisam是表鎖肤无；

innodb的表支持行鎖，這也是其支持事務(wù)的必要條件之一

2骇钦、可見innodb的表是非常依賴主鍵的了宛渐，所以如果主鍵不是按照自增的順序，那么在插入時(shí)，會(huì)出現(xiàn)B+樹更多的分裂窥翩，內(nèi)存找不到的又得找磁盤业岁，導(dǎo)致更多的磁盤IO；

這就是為什么寇蚊，innodb的表建議按業(yè)務(wù)無關(guān)的自增id作為主鍵笔时；

3、如果主鍵是一個(gè)特別長(zhǎng)的字符串之類東西仗岸，那么輔助鍵的索引允耿，葉子節(jié)點(diǎn)也都會(huì)存這些特別長(zhǎng)的主鍵，那么輔助鍵的索引扒怖，會(huì)很大较锡；

這就是為什么，innodb的表不建議主鍵使用特別長(zhǎng)的字段盗痒；

4蚂蕴、innodb的葉子存的是數(shù)據(jù)，比起myisam存的是地址俯邓，在寫時(shí)掂墓，原則上應(yīng)該會(huì)少一些磁盤IO，因?yàn)閙yisam還需要再去獲取數(shù)據(jù)看成；

上面介紹了基于B族樹存儲(chǔ)引擎的(mysql)的讀寫原理，結(jié)論是：不論是B樹跨嘉，還是B+樹川慌，在數(shù)據(jù)量很大時(shí)，隨機(jī)IO問題均無法良好處理祠乃；

3梦重、lsmtree引擎：

大量的隨機(jī)寫，導(dǎo)致B族樹在數(shù)據(jù)很大時(shí)亮瓷，出現(xiàn)大量磁盤IO琴拧，導(dǎo)致速度越來越慢，lsmtree是怎么解決這個(gè)問題的：

1嘱支、盡可能減少寫磁盤次數(shù)蚓胸；

2、即便寫磁盤除师，也是盡可能順序?qū)懀?/p>

方法：

1沛膳、對(duì)數(shù)據(jù)，按key劃分為若干level汛聚；

每一個(gè)level對(duì)應(yīng)若干文件锹安，包括存在于內(nèi)存中和落盤了的；

文件內(nèi)key都是有序的，同級(jí)的各個(gè)文件之間叹哭，一般也有序

如leveldb/rocksdb忍宋，level0對(duì)應(yīng)于內(nèi)存中的數(shù)據(jù)(0.sst)，后面的依次是1风罩、2糠排、3、...的各級(jí)文件(默認(rèn)到level6級(jí))

2泊交、寫時(shí)乳讥，先寫對(duì)應(yīng)于內(nèi)存的最低level的文件；這是之所以寫的快的一個(gè)重要原因

存在于內(nèi)存的數(shù)據(jù)廓俭，也是被持久化的以防丟失云石；

存在于內(nèi)存的數(shù)據(jù)，到達(dá)一定大小后研乒，被合并到下一級(jí)文件落盤汹忠；

3、落盤后的各級(jí)文件雹熬，也會(huì)定期進(jìn)行排序加合并(compact)宽菜，合并后數(shù)據(jù)進(jìn)入下一層level；

這樣的寫入操作竿报，大多數(shù)的寫铅乡，都是對(duì)一個(gè)磁盤頁順序的寫，或者申請(qǐng)新磁盤頁寫烈菌，而不再是隨機(jī)寫

所以總結(jié)lsmtree的寫為什么快的兩大原因：

1阵幸、每次寫，都是在寫內(nèi)存芽世；

2挚赊、定期合并寫入磁盤，產(chǎn)生的寫都是按key順序?qū)懠闷埃皇请S機(jī)查找key再寫荠割；

可見compact是個(gè)很重要的事情了，下面是基于lsmtree引擎的rocksdb的compact過程：

首先看一下rocksdb的各級(jí)文件組織形式：

然后旺矾，各級(jí)的每個(gè)文件蔑鹦，內(nèi)部都是按key有序，除了內(nèi)存對(duì)應(yīng)的level0文件宠漩，各級(jí)的內(nèi)部文件之間举反，也是按key有序的；

這樣扒吁，查找一個(gè)key火鼻，很方便二分查找(當(dāng)然還有bloomfilter等的進(jìn)一步優(yōu)化)

再然后室囊，每一級(jí)的數(shù)據(jù)到達(dá)一定閾值時(shí)，會(huì)觸發(fā)排序歸并魁索，簡(jiǎn)單說融撞，就是在兩個(gè)level的文件中，把key有重疊的部分粗蔚，合并到高層level的文件里

這個(gè)在lsmtree里尝偎，叫數(shù)據(jù)壓縮(compact)；

對(duì)于rocksdb鹏控，除了內(nèi)存那個(gè)level0到level1的compact致扯，其他各級(jí)之間的compact是可以并行的；通常設(shè)置較小的level0到level1的compact閾值当辐，加快這一層的compact

良好的歸并策略的配置抖僵，使數(shù)據(jù)盡可能集中在最高層(90%以上)，而不是中間層缘揪，這樣有利于compact的速度耍群；

另外，對(duì)于基于lsmtree的(rocksdb的)讀找筝，需要在各級(jí)文件中二分查找蹈垢，磁盤IO也不少，此外還需要關(guān)注level0里的對(duì)于這個(gè)key的操作袖裕，比較明顯的優(yōu)化是曹抬，通過bloomfilter略掉肯定不存在該key的文件，減少無謂查找急鳄；

附：

rocksdb vs leveldb：

1沐祷、rocksdb可以有多個(gè)memtable(level0的內(nèi)存文件的部分)；致力于解決寫速度快于compact速度的問題攒岛；

2、rocksdb支持merge operator操作胞锰，即用戶可以自定義對(duì)key的合并灾锯；

3、rocksdb支持多線程的compact(除了level0的內(nèi)存文件的部分)嗅榕；

4顺饮、rocksdb支持多個(gè)key查找(multiget)、范圍查找(rangeget)凌那；

5兼雄、rocksdb支持單進(jìn)程打開多個(gè)rocksdb實(shí)例；

6帽蝶、rocksdb支持在compact時(shí)根據(jù)key的有效期進(jìn)行濾除赦肋；