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

二叉樹

將新增數(shù)據(jù)插入左右兩邊，如果比節(jié)點(diǎn)數(shù)據(jù)要小，則放到左邊，比之大放到右邊。
但如果列數(shù)據(jù)一直遞增，那它就變成了一個(gè)鏈表結(jié)構(gòu)。當(dāng)要查詢某一數(shù)據(jù)時(shí)，需要一直遍歷該鏈表進(jìn)行查找，效率極低。

紅黑樹(二叉平衡樹)

紅黑樹又名平衡二叉樹，其本質(zhì)還是二叉樹，但其內(nèi)部會(huì)進(jìn)行平衡左右兩邊的數(shù)據(jù)，解決了普通二叉樹數(shù)據(jù)一直遞增最后成了鏈表的問題。
但如果數(shù)據(jù)量較大時(shí)，那它樹的高度會(huì)相當(dāng)高，查找次數(shù)即同樣相當(dāng)多，效率也很低。

B樹

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

B+樹

B樹的優(yōu)化版，非葉子節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)索引(冗余)，可以放更多的索引，葉子節(jié)點(diǎn)包含所有索引字段，葉子節(jié)點(diǎn)用指針連接，提高區(qū)間訪問的性能。
mysql一個(gè)葉節(jié)點(diǎn)存儲(chǔ)空間大小為16kb，最頂部葉子節(jié)點(diǎn)存儲(chǔ)的data，可能是真實(shí)的行數(shù)據(jù)，也可能是行數(shù)據(jù)所在的磁盤地址。

什么是索引

在關(guān)系型數(shù)據(jù)庫中，索引是一種排好序的數(shù)據(jù)結(jié)構(gòu)。它將數(shù)據(jù)提前按照一定的規(guī)則進(jìn)行排序或組織。能夠幫助快速定位到具體數(shù)據(jù)，加快數(shù)據(jù)表中數(shù)據(jù)的查找和檢索。
比方說：書本的目錄，文件夾、標(biāo)簽、房號(hào)等。都屬于是索引，都可以幫助我們快速進(jìn)行目標(biāo)數(shù)據(jù)的定位。

其本質(zhì)是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)思想是以空間換時(shí)間。

索引的總類

MySQL中的索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的，而不是服務(wù)器層。所以不同的存儲(chǔ)引擎具有不同的索引類型和實(shí)現(xiàn)，常見的索引分類如下

按照數(shù)據(jù)結(jié)構(gòu)分類：B+樹索引(所有引擎都支持，最常用)、Hash索引(僅Memory引擎)、Full-text索引(InnoDB、MyISAM)
按照物理存儲(chǔ)分類：聚集索引(InnoDB主鍵索引)、非聚集索引(MyISAM、InnoDB非主鍵索引)
按照字段特性分類：主鍵索引(primary key)、唯一索引(unique)、普通索引(index)、全文索引(fulltext)
按照字段個(gè)數(shù)分類：單列索引、聯(lián)合索引

B+樹索引

當(dāng)一個(gè)表沒有設(shè)置主鍵索引的時(shí)候，還會(huì)生成B+樹嗎？

答案是會(huì)的，在InnoDB引擎中，它會(huì)給每個(gè)表創(chuàng)建主鍵索引。如果沒有明確的主鍵索引，InnoDB會(huì)使用一個(gè)自動(dòng)生成的、隱藏的主鍵來創(chuàng)建索引（row_id）。
這個(gè)隱藏的主鍵索引使用的就是B+樹結(jié)構(gòu)，所以，InnoDB中，即使沒有明確的主鍵索引，也會(huì)創(chuàng)建一個(gè)B+樹索引。

Hash索引

【注】Hash索引在InnoDB中，不支持顯式的創(chuàng)建。雖然可以使用sql語句聲明Hash索引，但其實(shí)是不生效的，在底層仍然使用的是B+樹索引，Hash索引僅限于Memory引擎中。

比方說現(xiàn)在把表字段name聲明為Hash索引，假設(shè)此時(shí)有三條數(shù)據(jù)，分別是：張三、李四、李四。
Hash索引會(huì)將它們的名字通過Hash算法計(jì)算出一個(gè)Hash值，存放到一個(gè)槽里，然后對(duì)應(yīng)其數(shù)據(jù)。但此時(shí)的Hash值有可能沖突，比方說上面假設(shè)的同名“李四”。
此時(shí)會(huì)將數(shù)據(jù)存成一個(gè)鏈表，當(dāng)要查找name為“李四”時(shí)，首先找到對(duì)應(yīng) Hash的數(shù)據(jù)（鏈表），然后遍歷其鏈表，找到要找的值。
Hash索引
  優(yōu)點(diǎn)：只能用于等值比較，效率非常的高
  缺點(diǎn)：不支持范圍查詢，不支持排序，因?yàn)樗饕械姆植际菬o序的

聚集索引 和 非聚集索引

按照物理存儲(chǔ)分類：聚集索引(InnoDB)、非聚集索引(MyISAM)

test_innodb.frm  => Frame表結(jié)構(gòu)
test_innodb.ibd  => Innodb data表索引+數(shù)據(jù)

test_myisam  => Frame表結(jié)構(gòu)
test_myisam.MYD  => MyISAM data表數(shù)據(jù)
test_myisam.MYI  => MyISAM Index表索引

當(dāng)通過id查詢時(shí)，聚集索引比非聚集索引更快。非聚集索引的葉子節(jié)點(diǎn)只保存了數(shù)據(jù)個(gè)地址，當(dāng)查詢尋址找到對(duì)應(yīng)的目標(biāo)時(shí)，還需要通過該地址去找到對(duì)應(yīng)真正的數(shù)據(jù)
二級(jí)索引：InnoDB里面，非主鍵索引都是二級(jí)索引。例如，在user表，給age加了一個(gè)索引。此時(shí)這個(gè)即是二級(jí)索引，二級(jí)索引是非聚集索引，其他數(shù)據(jù)不存放在葉子節(jié)點(diǎn)上，葉子節(jié)點(diǎn)存放的是主鍵的id。當(dāng)通過二級(jí)索引查詢到指定數(shù)據(jù)時(shí)，會(huì)得到對(duì)應(yīng)主鍵的id，通過【回表】操作，重新找到該id的主鍵記錄，得到其數(shù)據(jù)，當(dāng)然了，如果只查詢id 比如：select id from user where age = 25，此時(shí)則不需要進(jìn)行回表了，因?yàn)槿~子節(jié)點(diǎn)存儲(chǔ)的已經(jīng)是對(duì)應(yīng)的id了，這個(gè)過程稱之為【索引覆蓋】，所以，在實(shí)際開發(fā)的過程中，應(yīng)盡量少使用select * 進(jìn)行查詢，通過【索引覆蓋】可以部分加快查詢。

單列索引 和 聯(lián)合索引

單列索引

假設(shè)現(xiàn)在有user表，字段有：id，name，age，sex。
此時(shí)給name字段設(shè)置了一個(gè)普通非唯一索引：alter table `test`.`user` add index (`name`)，那么name就是索引列，同時(shí)也是單列索引

聯(lián)合索引

區(qū)別于聯(lián)合索引，假設(shè)上面的例子中，給name和age建立一個(gè)聯(lián)合索引:alter table `test`.`user` add index (`name`,`age`,`sex`)。
當(dāng)排序時(shí)，是先給name進(jìn)行排序，name相同時(shí)接著給age排序，如果還有其他的列時(shí)，以此類推，最后再以id來排

最左前綴原則：當(dāng)創(chuàng)建了聯(lián)合索引的時(shí)候，想要索引生效的話，必須要帶上最左的字段，例如例子中的name，只能使用：name/age、name/age/sex、name/sex 三種組合。例如：select name,age,sex from user where name = '張三' and age = 12
聯(lián)合索引的優(yōu)勢
減少開銷：建立一個(gè)(a,b,c)，實(shí)際相當(dāng)于建立了(a),(a,b),(a,b,c)三個(gè)索引，每多一個(gè)索引，都會(huì)增加寫操作的開銷和磁盤空間的開銷，當(dāng)在大數(shù)據(jù)量的表，使用聯(lián)合索引會(huì)大大減少開銷。
覆蓋索引：select 不使用*，而是直接指定聯(lián)合索引的字段，此時(shí)查詢出結(jié)果后，不需要進(jìn)行回表而能直接得到數(shù)據(jù)，在實(shí)際的應(yīng)用中，覆蓋索引是主要提升性能的優(yōu)化手段之一。
效率更高：相對(duì)于單列索引，當(dāng)假設(shè)要查詢name、age、sex字段時(shí)，假設(shè)設(shè)置了3個(gè)單列索引，在找到數(shù)據(jù)時(shí)，因?yàn)槠洳⒎侵麈I索引，葉子節(jié)點(diǎn)存放的只是主鍵id，因此還需要多次通過該索引得到的id回表得到整條數(shù)據(jù)的內(nèi)容，而聯(lián)合索引只需要回表一次即可得到整條的數(shù)據(jù)內(nèi)容

索引的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

1.提交檢索效率，更快的查詢出結(jié)果
2.降低排序的成本，索引對(duì)應(yīng)的字段都有一個(gè)自動(dòng)排序功能，默認(rèn)升序asc

缺點(diǎn)

1.創(chuàng)建和維護(hù)索引需要耗費(fèi)時(shí)間，這種時(shí)間隨著數(shù)據(jù)量的增加而增加
2.索引需要物理存儲(chǔ)空間，數(shù)據(jù)量越大，所需的空間越大
3.降低數(shù)據(jù)表增刪改的效率，因?yàn)槊看卧鰟h改，索引都要進(jìn)行動(dòng)態(tài)維護(hù)其樹結(jié)構(gòu)

為什么建議InnoDB表必須建主鍵，并且推薦使用整形的自增主鍵？

建主鍵

如果不建主鍵，則mysql內(nèi)部會(huì)根據(jù)列數(shù)據(jù)去構(gòu)成一個(gè)B+樹索引。
如果所有列都不滿足，則自動(dòng)生成一個(gè)隱藏列來構(gòu)建，不但空耗空間，還因?yàn)槭请[藏列外部無法使用，故而自己使用主鍵為更優(yōu)解

整形

效率更高(直接比較整形比ASCII碼后比較更快)且更節(jié)省空間

自增

因?yàn)閎+樹索引為排序后的，如果不是自增，則可能需要在某兩個(gè)數(shù)據(jù)間插入一條新數(shù)據(jù)，可能導(dǎo)致節(jié)點(diǎn)分裂。
而自增則在最后面累加即可，前者效率會(huì)更高，而使用uuid的話，可能會(huì)高頻出現(xiàn)從中間插入數(shù)據(jù)，非常影響性能。
但如果是偶爾從中插入，這種情況是可以的，比方說分庫分表中用到的【雪花算法生成id】，它是趨勢遞增的，偶爾會(huì)從中間插入