在上一期講存儲的末尾锣尉，我們留了一個坑浮庐。雖然通過列存，能夠避免讀取不必要的數(shù)據(jù)(沒使用的列)來提高查詢速度否淤，但是對于下面這類點查詢(point query)荐吵，還能不能進一步優(yōu)化呢先紫？
SELECT * FROM titanic_survivor WHERE age = 10;
答案是肯定的，解決方案就是今天的主題 -- 索引(index)糊肤。
索引這個概念在我們?nèi)粘Ｉ钪泻艹Ｒ娭蟆１热缭诤芏鄷淖詈髥福寂溆嘘P鍵字索引。它能幫助你快速地找到某個關鍵字所在的書頁嗡贺。試想一下隐解，如果沒有索引，想要查詢某個關鍵字所在的章節(jié)和書頁诫睬，可能唯一的辦法就是一頁一頁翻書直到找到為止煞茫。索引大大提高了查詢的速度！
數(shù)據(jù)庫的索引也正是為了解決這類問題：索引通過引入冗余的數(shù)據(jù)存儲(類比書籍最后的索引章節(jié))，以此來提高查詢語句的速度续徽。和上一期的結構類似蚓曼，相較于列舉不同索引類型的分類法，我們依然從解決問題的角度來看不同類型的索引是為了解決哪些查詢而演化而來的钦扭。
回到上面這個點查詢語句纫版，你能想到什么辦法來優(yōu)化執(zhí)行？我們沿用上一期titanic_survivor的數(shù)據(jù)(下圖)客情，一起來看其弊。
讀者可能很容易就會想到，我們可以建立一個哈希表(HashMap)膀斋。哈希表的鍵(key)存儲age的值梭伐，哈希表的值(value)存儲所有age為對應鍵值的row在存儲系統(tǒng)中的相對位置(如果使用csv文件存儲，它就是row的行號概页。如果用字節(jié)流存儲數(shù)據(jù)籽御，它就是row對應于文件中的offset)。下圖是對于titanic_survovior的age列作索引惰匙。
有了這樣一個哈希表，當需要查詢年齡是35的幸存者時铃将，只需要讀取行4和行5的數(shù)據(jù)即可项鬼。(可能對于csv文件比較難描述這類優(yōu)化。設想當數(shù)據(jù)文件是按字節(jié)流存儲時劲阎，可以用隨機文件讀取的API來讀取很小一部分數(shù)據(jù)) 雖然隨機讀取的平均效率遠低于順序讀取(因為文件系統(tǒng)需要尋道seek)绘盟，但相比于讀取2行數(shù)據(jù)和一百萬行數(shù)據(jù)，前者的速度毋庸置疑得快悯仙。
這樣一個哈希表龄毡，就引出了第一類索引，哈希索引(Hash Index):?根據(jù)需要索引的列(并不限制為一個列锡垄，可以是多個列的組合)沦零，建立一個哈希表。讀取數(shù)據(jù)時货岭，先根據(jù)索引列的鍵值找到對應的數(shù)據(jù)位置路操，然后讀取相應數(shù)據(jù)。
本文不是數(shù)據(jù)結構101千贯，就不具體討論如何實現(xiàn)哈希函數(shù)屯仗，解決鍵沖突，對哈希表進行擴容縮容等的問題了搔谴。稍微聊一些工程實踐中的細節(jié)：選擇哈希函數(shù)的指標魁袜，肯定是速度越快越好。在輸入和輸出值域相同的情況下，沖突概率越低越好峰弹。下面列舉了一些開源且受歡迎的哈希函數(shù)實現(xiàn)店量，有興趣的同學可以深入學習：
1) MurmurHash (2008):https://en.wikipedia.org/wiki/MurmurHash
2) Google CityHash (2011):https://opensource.googleblog.com/2011/04/introducing-cityhash.html
3) Google FarmHash (2014):https://opensource.googleblog.com/2014/03/introducing-farmhash.html
4) CLHash (Carry-less) (2016):https://arxiv.org/abs/1503.03465
有同學提出疑問，提到哈希算法垮卓， 最先想到的就是MD5, SHA等的算法垫桂，為什么這里并沒有提及。因為這類算法被稱為密碼哈希算法(當然MD5已經(jīng)多次被證明不安全了粟按，請不要繼續(xù)用于加密诬滩。。)灭将。為了追求安全性疼鸟，這類算法具備特別的屬性，比如難以從一個已知的哈希值去逆推原始的消息以及雪崩效應(Avalanche effect): 即輸入發(fā)生微小變化也會導致輸出的不可區(qū)分性改變庙曙，從而犧牲了哈希運算的效率空镜。建立哈希索引時并不需要這類安全屬性，因此會選擇性能更高的哈希算法捌朴。
著名的開源數(shù)據(jù)庫Postgres就支持哈希索引吴攒，生成語句如下：
（CREATE INDEX index_name ON table_name USING HASH (column_name);
但在對應的文檔中，卻明確指出了不建議使用哈希索引砂蔽。至于原因洼怔，我們先賣個關子，過一會再詳解左驾×土ィ總結一下，為了提高點查詢的效率诡右，我們引入了第一類索引安岂，哈希索引。
哈希索引雖好帆吻，卻也不是萬能的域那。比如把查詢條件從點查詢改為范圍查詢，如下所示：
SELECT * FROM titanic_survivor WHERE age BETWEEN 1 AND 10;
有同學說桅锄，依然可以用哈希索引解決琉雳，只要做10次哈希索引的查詢即可。那我做得再絕一些:
SELECT * FROM titanic_survivor WHERE age > 10;
或者干脆把age換成浮點類型友瘤。如此翠肘，哈希索引是萬萬沒轍了吧。
面對這類查詢辫秧，有什么方法可以提高速度呢束倍？有讀者會想到，如果把要查詢的列(此為age)進行排序，然后進行二分查找來定位绪妹，依次掃描列中滿足條件的數(shù)據(jù)甥桂，就可以避免全文件掃描了。沿用上面的示例邮旷，我們對titanic_survivor的age列排序黄选，并且紀錄相應的行號, 如下圖所示：
假設需要查詢年齡在20至40歲之間的幸存者，可以通過二分查找先定位到年齡22婶肩，然后依次順序讀取之后26办陷，35和38歲的對應行的數(shù)據(jù)，當搜索至54歲時停止即可律歼。概括一下方法：對相關列進行排序民镜，用二分查找來快速定位然后順序查詢。二分查找1至100萬中的某個數(shù)需要20次查詢(2^20約等于100萬)险毁，有什么方法可以再進一步提高效率制圈？于是我們引出第二個使用的數(shù)據(jù)結構B樹和B+樹(B - tree, B+ - Tree)。
關于B樹和B+樹的具體實現(xiàn)細節(jié)畔况，請參考相關數(shù)據(jù)結構書籍資料鲸鹦，這里就不贅述了。簡單而言跷跪，B樹相當于把二分查找變成了N分查找亥鬓，假設N為100，那查找范圍為(1, 100萬)就只需要3次分叉了(100^3 = 100萬)域庇。B+樹和B樹的區(qū)別就在于B樹在非葉節(jié)點也會存儲數(shù)據(jù)而B+樹僅在頁節(jié)點存儲數(shù)據(jù)。下圖示例為B+樹覆积。
這類索引就稱之為B樹索引听皿。B樹和B+樹通過引入有很多分枝的樹節(jié)點來提高定位速度以此來提高整體查詢速度，算得上是空間換時間的方法宽档。同樣尉姨，在工程中還有很多可優(yōu)化的細節(jié)。比如對于B+樹吗冤，只有頁節(jié)點存儲具體的數(shù)據(jù)信息又厉，內(nèi)節(jié)點和根節(jié)點僅僅是用于快速定位，因此衍生出了合并前綴(prefix compression)以及刪除無用后綴(suffix truncation)等的優(yōu)化方法椎瘟。再舉個常見的優(yōu)化示例覆致，B+樹的頁節(jié)點原本用來存儲對應列值的行在數(shù)據(jù)文件中的相對位置，所以讀取完索引后還需要根據(jù)相對位置去數(shù)據(jù)文件中讀取數(shù)據(jù)肺蔚。但對于固定的查詢語句煌妈，可以提前知道其他哪些列也會經(jīng)常被查詢，把這些列的數(shù)據(jù)直接存儲在索引中，進一步用空間來省去讀取數(shù)據(jù)文件的時間璧诵。比如汰蜘，如果我們想要更進一步優(yōu)化下面這個語句：
SELECT sex FROM titanic_survivor WHERE age > 10;
就可以把性別的信息存放在索引中。對應的SQL語句如下
CREATE INDEX btree_idx_age ON titanic_survivor(age) USING BTREE INCLUDE (sex);
為了能夠進一步優(yōu)化范圍查詢之宿，我們引出了第二類索引族操，B樹索引。現(xiàn)在可以聊聊上面埋下的伏筆為什么Postgres并不建議使用哈希索引了比被。貼出原文(From Postgres 7.2 Doc)：
Because of the limited utility of hash indexes, a B-tree index should generally be preferred over a hash index. We do not have sufficient evidence that hash indexes are actually faster than B-trees even for = comparisons. Moreover, hash indexes require coarser locks.
可見色难，雖然從理論上講，對于點查詢姐赡，哈希索引應該更快莱预，而且存儲空間相對B樹索引更少。但是通過工程中的優(yōu)化项滑，可以讓B樹索引在點查詢中也毫不遜色依沮。聊完了哈希索引和B樹索引，留一個思考題給讀者：拋開性能不說枪狂，用B樹索引讀取數(shù)據(jù)還能帶來一個隱形的好處危喉，猜猜是什么好處？我會把答案留在本文的最后州疾。
說了這么多B樹索引的優(yōu)勢辜限，它有什么缺陷嗎？B樹的實現(xiàn)严蓖，增加和刪除數(shù)據(jù)會牽涉到節(jié)點的分離和合并薄嫡，是比較復雜的(沒有同學在面試過程中遇到要求實現(xiàn)B樹這類的變態(tài)問題吧)。尤其是在高并發(fā)的環(huán)境下颗胡，對于節(jié)點的操作需要加鎖毫深， 會進一步導致速度變慢。有沒有辦法進一步改進嗎毒姨？有哑蔫！有一種比較偏門的數(shù)據(jù)結構 -- 跳表(skip list:https://en.wikipedia.org/wiki/Skip_list)比B樹在這方面就更優(yōu)秀。跳表的實現(xiàn)是一個多層次的鏈表弧呐，底部鏈表和B樹一樣是一列有序的鍵值對闸迷，通過在上層加入更松散的有序鏈表來支持跳躍查詢(命名的由來)。下圖給出了跳表示例俘枫。
理論上的時間復雜度和B樹是類似的腥沽。但為什么說跳表對于高并發(fā)更好呢，我自己的理解是因為在新增節(jié)點時崩哩，跳表通過一個概率值來決定是否需要添加上層節(jié)點巡球，實現(xiàn)起來言沐，變化比較局部，不會有B樹那樣牽一發(fā)而動全身的變化酣栈，所以無論是加鎖實現(xiàn)险胰，還是無鎖實現(xiàn)都對高并發(fā)支持更好。如果想要了解更多矿筝，請各位同學自行查閱起便。跳表的另一個優(yōu)勢在于實現(xiàn)中對于內(nèi)存的需求相對于B樹更少〗盐可能這也是為什么內(nèi)存數(shù)據(jù)庫MemSql就支持跳表索引榆综。其實跳表也有缺點，因為是用鏈表實現(xiàn)铸史，所以對于緩存并不是很友好鼻疮。另一個缺點是，要支持逆向查詢琳轿，比如(age < 40)判沟，這就需要用雙向鏈表實現(xiàn)，復雜度也會更高崭篡。
總結一下挪哄，為了更好得支持并發(fā)操作以及內(nèi)存優(yōu)化，我們引入了跳表索引琉闪。
B樹索引還有哪些情況是不適用的嗎迹炼？現(xiàn)在假設我們要對性別或者艙位做索引，但這些列本來基數(shù)(distinct value cardinality)就非常小颠毙，B樹帶來的快速定位優(yōu)勢就沒有意義了斯入。有什么索引是適合這類查詢嗎？引出我們今天最后的一類索引 -- 位圖索引蛀蜜。
位圖索引專門針對基數(shù)很小的列來做索引咱扣。比如對于性別，我們可以生成下列的索引:
在查詢時涵防，只要讀取位圖為1的行即可。有些情況下沪铭，位圖索引也支持多條件查詢壮池，比如針對下列查詢語句
SELECT * FROM titanic_survivor WHERE sex = 'female' AND cabin = 'A'
我們可以同時對sex和cabin做位圖索引，然后對sex:female和cabin:A進行位圖與操作再讀取結果為1的行即可杀怠。除此之外椰憋，位圖索引的另一大優(yōu)勢在于，相對于其他索引赔退，存儲需求很谐纫馈：對于每個基數(shù)证舟，每一行數(shù)據(jù)只要1bit的存儲。所以當列的基數(shù)很大時窗骑，位圖索引就失去意義了女责。位圖索引的另一個劣勢在于，不適用于高并發(fā)環(huán)境创译，因為任何修改和添加抵知，都需要對索引文件進行加鎖。
針對基數(shù)較小的列软族，我們引入了位圖索引來提高查詢速度刷喜。
小結
數(shù)據(jù)庫索引是用來進一步提高查詢語句的速度。針對不同的數(shù)據(jù)環(huán)境和不同索引的優(yōu)缺點立砸，我們介紹了以下這些方法：
1） 引入哈希索引用來提高點查詢效率
2） 引入B樹索引用來提高范圍查詢
3） 針對B樹索引對高并發(fā)支持的詬病掖疮，引入跳表索引
4） 針對基數(shù)較小的列，引入位圖索引
使用索引時颗祝，可以對每個表創(chuàng)建一個或多個索引浊闪。讀者可能會有疑問，那豈不是對每個列都創(chuàng)建索引吐葵，就是萬事大吉了规揪。答案是否定的。索引是否能夠提升效率温峭，取決于查詢語句以及數(shù)據(jù)的分布猛铅。而是否決定使用索引，是由數(shù)據(jù)庫的優(yōu)化器(之后會有專門的章節(jié)介紹優(yōu)化器)決定的凤藏。另外奸忽，天下沒有免費的午餐。首先揖庄，索引是冗余的數(shù)據(jù)存儲栗菜，是要占據(jù)內(nèi)存和磁盤空間的。二蹄梢，索引數(shù)據(jù)要和表數(shù)據(jù)同步疙筹，在對修改數(shù)據(jù)的同時，也需要同步更新索引禁炒。如果索引太多而咆，會大大降低數(shù)據(jù)導入和修改的吞吐量(可以在Postgres中做小實驗，在有和沒有索引的情況下幕袱，導入數(shù)據(jù)的時間相差甚遠)暴备。工程實踐中，一般會在數(shù)據(jù)更新操作全部完成以后们豌，再對表建索引涯捻。如何正確創(chuàng)建的索引浅妆，是原先DBA的工作；一個有經(jīng)驗的DBA障癌，能夠根據(jù)查詢需求創(chuàng)建最高效的索引凌外。在越來越智能的數(shù)據(jù)庫時代，很多數(shù)據(jù)庫已經(jīng)可以根據(jù)查詢語句的類型混弥，來提供創(chuàng)建索引的建議趴乡，畢竟沒有數(shù)據(jù)庫比數(shù)據(jù)庫本身更懂自己！
寫文章的時候正好是2月14日情人節(jié)蝗拿，請允許我撒一波狗糧晾捏。小葡萄，馬上就要到咱們的一周年紀念啦哀托。感謝你在地球上找到我惦辛，選中我，陪伴我仓手。愛你呢胖齐！沒有你，也不會有這一系列博文(請參考系列第一篇查梗)嗽冒。
下面揭露思考題答案(是不是以為我光記得撒狗糧呀伙，把這個給忘了)：用B樹索引讀取數(shù)據(jù)的另一個好處是什么？那就是讀取的數(shù)據(jù)針對索引列是排過序的添坊。這可是一個非常好的特性剿另，假設查詢語句中本來就有排序需求(SQL關鍵字ORDER BY), 就不用再對數(shù)據(jù)進行排序了。另外有序列對于數(shù)據(jù)表的聯(lián)合(join)贬蛙，以及聚類(aggregation)都很有幫助雨女，這些我們留到以后再介紹。
下期再見阳准！
