程序員經(jīng)典面試題,為什么數(shù)據(jù)庫索引多用B+樹
最近很多小伙伴都參與了面試更換了工作,校招也已經(jīng)開始了。最近面試了幾個實習(xí)生,感覺基礎(chǔ)能力都不大行,數(shù)據(jù)庫在程序員的面試中占有舉足輕重的一個作用。今天我們來講一講數(shù)據(jù)庫的索引是什么?
索引,就跟我們的書本的目錄一樣,如果一本書沒有目錄,那么你要找某一個知識點,那自然是相當(dāng)費勁的。數(shù)據(jù)庫的索引就是扮演這樣的角色,索引會告訴你對應(yīng)的數(shù)據(jù)存放的磁盤地址,就好比目錄上面的頁數(shù)。那么數(shù)據(jù)庫的“目錄”究竟長什么樣子呢?
常見的數(shù)據(jù)庫索引有下面三種類型,第一是哈希表,哈希表相信大家都已經(jīng)不陌生了,我們可以將數(shù)據(jù)庫的索引字段后哈希并保存下來。只要哈希算法設(shè)計得合理,我們可以非常快地找到對應(yīng)數(shù)據(jù)的一個存放地址,然后到對應(yīng)的存放地址就可以快速地找到數(shù)據(jù)。那么,哈希索引有什么缺點呢?首先是哈希表比較適合在內(nèi)存中使用,但是如果要落盤,就比較麻煩了,特別是哈希表擴容的時候,磁盤的很多數(shù)據(jù)都會修改。第二,哈希表沒辦法進(jìn)行一個區(qū)間的篩選。
第二種則是數(shù)組索引,與上述的哈希表類似,但又有所不同。與哈希索引類似,數(shù)組索引的效率也是非常高的,在一個有序數(shù)組里面去查找元素,我們只要進(jìn)行二分查找即可。但是數(shù)組索引的問題也是非常地明顯,那便是插入非常的麻煩,你插入一個新的元素,就要把后面所有的元素都往后移動一下。所以,數(shù)組索引我們一般只有靜態(tài)數(shù)據(jù)才會使用。
有序數(shù)組都講了,那么接下來肯定就是二叉樹了,我們說的二叉樹當(dāng)然是二叉排序樹,二叉排序樹相對與數(shù)組,比較大的優(yōu)點是方便插入。但是同時也存在這么一個問題,因為索引的數(shù)據(jù)可能存在磁盤,那么如果索引的數(shù)據(jù)超過1000條的時候,就有可能要經(jīng)過10次才能夠找到最終的數(shù)據(jù),而磁盤IO的瓶頸在于尋道跟旋轉(zhuǎn),效率必然會降低。所以,我們要盡量地減少在磁盤中尋道跟旋轉(zhuǎn)的次數(shù),所以多叉樹就被廣泛應(yīng)用在數(shù)據(jù)庫索引當(dāng)中了。而在多叉樹中,比較常被使用的,便是B+樹。

現(xiàn)在你知道了為什么數(shù)據(jù)索引有哪些,以及為什么B+樹被廣泛應(yīng)用的道理了吧。歡迎大家關(guān)注我,共同學(xué)習(xí),共同進(jìn)步。大家的支持是我繼續(xù)嘮嗑的動力。




























