一．數(shù)據(jù)結(jié)構(gòu)

1.?二叉樹

特點(diǎn)：左側(cè)子節(jié)點(diǎn)比父節(jié)點(diǎn)小，右側(cè)子節(jié)點(diǎn)比父節(jié)點(diǎn)大(對于同一個父節(jié)點(diǎn)下的兩個子節(jié)點(diǎn))

缺點(diǎn)：對于一直遞增得數(shù)據(jù)不能存在該數(shù)據(jù)結(jié)構(gòu)中，會變成鏈表，不能降低樹的高度

圖 1-1

?

圖1-2

2.?紅黑樹

特點(diǎn)：左側(cè)子節(jié)點(diǎn)比父節(jié)點(diǎn)小，右側(cè)子節(jié)點(diǎn)比父節(jié)點(diǎn)大、或者相等(對于同一個父節(jié)點(diǎn)下的兩個子節(jié)點(diǎn))，對于一直遞增的數(shù)據(jù)可以自動平衡

缺點(diǎn)：對于百萬條數(shù)據(jù)，樹的高度還是太高

3.?Hash表

優(yōu)點(diǎn)：對數(shù)據(jù)進(jìn)行Hash(散列)運(yùn)算，主流的Hash算法有MD5、SHA256等等，然后將哈希結(jié)果作為文件指針可以從索引文件中獲得數(shù)據(jù)的文件指針，再到數(shù)據(jù)文件中獲取到數(shù)據(jù)，按照這樣的設(shè)計，我們在查找where Col2 = 22的記錄時只需要對22做哈希運(yùn)算得到該索引所對應(yīng)那行數(shù)據(jù)的文件指針，從而在MySQL的數(shù)據(jù)文件中定位到目標(biāo)記錄，查詢效率非常高。

缺點(diǎn)：無法解決范圍查詢(Range)的場景，比如 select count(id) from sus_user where id>10；因此Hash這種索引結(jié)構(gòu)只能針對字段名=目標(biāo)值的場景使用。不適合模糊查詢(like)的場景

4.?B-樹

特點(diǎn)：葉節(jié)點(diǎn)具有相同的深度，葉節(jié)點(diǎn)的指針為空，所有索引元素不重復(fù)，節(jié)點(diǎn)中的數(shù)據(jù)從左到右遞增排列

缺點(diǎn)：存儲的數(shù)據(jù)量沒有B+樹多，B樹不支持range-query

(區(qū)間查詢)

? ? ? ? ? ? ? ? ?

圖1-3

5.?B+樹

特點(diǎn)：非葉子節(jié)點(diǎn)不存儲data,只存儲索引(冗余)，可以放更多的索引，葉子節(jié)點(diǎn)包含所有索引字段，葉子節(jié)點(diǎn)用指針鏈接，提高區(qū)間訪問的性能。

與B-樹對比：B+樹有一個最大的好處，方便掃庫，B樹必須用中序遍歷的方法按序掃庫，而B+樹直接從葉子結(jié)點(diǎn)挨個掃一遍就完了，B+樹支持range-query(區(qū)間查詢)非常方便，而B樹不支持。

?

圖 1-4

總結(jié)

以上是生活随笔為你收集整理的mysql数据结构_mysql的底层数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。