堆（heap）結(jié)構(gòu)比較于B樹(shù)的優(yōu)缺點(diǎn)是什么?

一、堆（heap）結(jié)構(gòu)比較于B樹(shù)的優(yōu)缺點(diǎn)

堆（heap）結(jié)構(gòu)比較于B樹(shù)的優(yōu)缺點(diǎn)是堆只能訪問(wèn)一個(gè)元素，也就是堆頂，其他的元素在堆里是無(wú)意義的。優(yōu)點(diǎn)也是這個(gè)，既然用堆了，那就是想訪問(wèn)堆頂，查詢(xún)復(fù)雜度O(1)。B樹(shù)每個(gè)節(jié)點(diǎn)都有意義，但訪問(wèn)特定的元素要進(jìn)行中序遍歷，肯定比堆慢。

堆

堆（heap）組織表數(shù)據(jù)行在堆中存儲(chǔ)，沒(méi)有任何特定順序，向一個(gè)全新的沒(méi)有做過(guò)更新和刪除的堆中插入一行時(shí)候，總是 append 到堆表文件的最后一頁(yè)當(dāng)中。因?yàn)椴挥每紤]排序，所以插入速度會(huì)比較快。

但是要查找符合某個(gè)條件的記錄，就必須得讀取全部的記錄以便篩選。而這個(gè)時(shí)候?yàn)榱思涌觳樵?xún)速度，索引就出現(xiàn)了，索引是針對(duì)少量特定字段的值拿出來(lái)進(jìn)行排序存儲(chǔ)，存儲(chǔ)索引 key 以及數(shù)據(jù)行在堆表上面的絕對(duì)位置（頁(yè)號(hào)，頁(yè)內(nèi)偏移），而因?yàn)樗饕怯行虻?，所以就?huì)很容易通過(guò)索引查詢(xún)到具體的記錄位置（普遍使用二分查找法），然后再根據(jù)記錄位置直接從表中讀取該記錄。同時(shí)因?yàn)樗饕淖侄屋^少，所以索引通常會(huì)比其基表小得多。

從上面通過(guò)索引訪問(wèn)表記錄的方式可以看出，當(dāng)要訪問(wèn)的數(shù)據(jù)量較大時(shí)，通過(guò)每一條記錄的位置去訪問(wèn)原始記錄，每一條符合條件的記錄都需要經(jīng)過(guò)索引訪問(wèn)后再訪問(wèn)基表這樣一個(gè)復(fù)雜的過(guò)程，這會(huì)花費(fèi)很多時(shí)間。同樣，如果不經(jīng)過(guò)索引而直接查詢(xún)表，也可能因?yàn)楸碜侄翁?，記錄較大的情況下把全部的數(shù)據(jù)讀取進(jìn)來(lái)，這也會(huì)花費(fèi)很多時(shí)間。

那怎么辦呢？這個(gè)時(shí)候就會(huì)想到，如果表中數(shù)據(jù)本身就是有序的，這樣查詢(xún)表的時(shí)候就可以快速的找到符合條件的記錄位置，而很容易判斷符合條件記錄的位置，這樣只需要讀取一小部分?jǐn)?shù)據(jù)出來(lái)就可以了，不需要全表記錄都讀取出來(lái)進(jìn)行判斷。索引組織表就這樣產(chǎn)生了，當(dāng)然索引表中插入，更新的時(shí)候可能會(huì)因?yàn)樾枰判蚨鴮?shù)據(jù)重組，這時(shí)候數(shù)據(jù)插入或更新速度會(huì)比堆組織表慢一些。如果堆組織表上有索引，那么對(duì)堆組織表的插入也會(huì)因?yàn)橐薷乃饕兟?/p>

由于堆表的索引只存儲(chǔ)索引 key 以及數(shù)據(jù)行在堆表上面的絕對(duì)位置（頁(yè)號(hào)，頁(yè)內(nèi)偏移），如果這行記錄發(fā)生了更新，并且不能原地更新，需要進(jìn)行遷移，那么就會(huì)發(fā)生一個(gè)情況，堆表所有索引都需要修改，指向新的行位置。而索引組織表就不需要這個(gè)開(kāi)銷(xiāo)，更新只會(huì)新插入變化了的索引 key，不變的索引 key 不需要新插入，只有當(dāng)主鍵發(fā)生更改才需要對(duì)應(yīng)修改其他二級(jí)索引，通常主鍵也不會(huì)更新，所以這也就是索引組織表更新效率更高的由來(lái)。

但一般使用堆表的數(shù)據(jù)庫(kù)都不會(huì)直接這么更新，代價(jià)太大了。而是會(huì)在數(shù)據(jù)頁(yè)預(yù)留一些空間，當(dāng)遇見(jiàn)不能原地更新的記錄時(shí)，就會(huì)在這個(gè)頁(yè)中新插入一條更新后的記錄，然后在這個(gè)頁(yè)中做一個(gè)指針把老記錄指向新紀(jì)錄，這樣就不用更新索引信息了。當(dāng)然，如果你這個(gè)頁(yè)中沒(méi)有空閑空間可以插入新的記錄，那么還是需要做行遷移，然后更新所有索引。

延伸閱讀：

二、堆表和索引組織表的比較

堆表的特點(diǎn)就是索引和數(shù)據(jù)分開(kāi)，所有索引都是二級(jí)索引，或叫輔助索引。所以主鍵索引也是二級(jí)索引，沒(méi)有完整記錄，區(qū)別只有少數(shù)或非少數(shù)。索引中存儲(chǔ)的是 key 與指針，指針指向具體數(shù)據(jù)記錄。當(dāng)然，查找 key 的算法都是一樣的，使用二分查找，也叫書(shū)簽查找。

跟索引組織表相比，堆表有什么好處呢？其實(shí)主要就是通過(guò)主鍵或二級(jí)索引查詢(xún)，開(kāi)銷(xiāo)是一樣的。都是通過(guò)先找到key，然后定位到數(shù)據(jù)。而索引組織表，由于二級(jí)索引是指向主鍵，所以查詢(xún)二級(jí)索引需要先定位到 key，然后拿到主鍵 id，還要根據(jù)主鍵 id 再次通過(guò)二分查找定位到真正的數(shù)據(jù)頁(yè)。當(dāng)然，索引組織表通過(guò)主鍵查詢(xún)開(kāi)銷(xiāo)與堆是一樣的。從索引組織表的工作方式可以看出，索引組織表必須要有主鍵，如果非顯式創(chuàng)建，InnoDB 存儲(chǔ)引擎會(huì)默認(rèn)創(chuàng)建一個(gè) ROWID 當(dāng)做主鍵；而堆表則無(wú)強(qiáng)制要求。