概要

oracle市場份額在降低，mysql變得越來越重要

樣本數(shù)據(jù)可以使用 sakila 數(shù)據(jù)庫

你會怎么設(shè)計索引？

加索引目的是快速查找數(shù)據(jù)，最終要快速從文件中快速獲取一條記錄。
如果使用id+偏移量+數(shù)據(jù)文件作為索引，會使得索引文件非常大，然后需要給索引文件加索引
于是會產(chǎn)生索引，索引的索引，索引的索引的索引...

OLAP：對歷史數(shù)據(jù)的分析，比如Hive
OLTP：關(guān)系型數(shù)據(jù)庫都是OLTP，要求在最短時間內(nèi)返回最終結(jié)果

為什么選擇B+樹？
MySQL B+ 樹的根節(jié)點、葉子結(jié)點都存儲與磁盤中。加載時，優(yōu)先將根節(jié)點加載至內(nèi)存中。現(xiàn)在PC的內(nèi)存大了，可以將所有的非葉子結(jié)點都加載進內(nèi)存中。

局部性原理
空間局部性、時間局部性、磁盤預(yù)讀（一次讀一頁，通常操作系統(tǒng)設(shè)定為為4k）
應(yīng)用程序也能自己設(shè)定頁的大小，innodb一頁為16kb

索引是什么？

存儲引擎是不同的數(shù)據(jù)表在文件系統(tǒng)中的組織形式。

不同存儲引擎之間的區(qū)別
常見存儲引擎： innodb, myisam, memory…

數(shù)據(jù)組織的形式不同；
innodb支持事務(wù)，myisam不支持事務(wù)
innodb支持行鎖+表鎖，myisam只支持表鎖

innodb這么好，為什么還要有myisam？
myisam的查詢、計算效率較高。
mysql誕生以來，只有myisam。innodb是后來以插件的形式集成到mysql中，現(xiàn)在默認是innodb

其他幾種數(shù)據(jù)結(jié)構(gòu)

Hash索引

memory存儲引擎在使用Hash索引。innodb默認使用B-tree，但根據(jù)官網(wǎng)文檔，Memory tables也支持哈希索引。

Hash劣勢：rehash，哈希沖突問題。不好的hash算法導(dǎo)致散列不均勻，浪費磁盤空間。
jdk1.8的哈希函數(shù)算法使用了擾動函數(shù)，也是為了讓散列更均勻

二叉樹

提升IO效率：減少IO次數(shù)、減少IO量（生產(chǎn)中SQL語句中不要隨意用*匹配，應(yīng)該只取有用數(shù)據(jù)）
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
二叉樹：如果在插入的時候排序，形成BST（二叉搜索樹）

二叉搜索樹
插入遞增時，退化成鏈表：

AVL（二叉平衡樹）
最長路徑、最短路徑之差不能超過1，是一棵嚴格的平衡樹，插入過程中需要頻繁旋轉(zhuǎn)，插入性能高，查詢性能低。

紅黑樹
不是一棵嚴格意義上的平衡樹，是相對平衡。
紅黑樹的最長路徑只要不超過最短路徑的2倍即可。
還有一些其他限制…
但也存在存數(shù)較高的問題

層數(shù)高，問題在于一個節(jié)點中有且只有兩個分支。于是有了B樹：

B樹

Degree用來表示每一個節(jié)點中最多能放多少條數(shù)據(jù)。

MySQL中的層高是由數(shù)據(jù)量決定的，無法人為控制。3層高，千萬數(shù)據(jù)量都能存放進去。

一個磁盤16kb，一條數(shù)據(jù)1kb，假設(shè)其他指針不占用空間，每個空間能放16條數(shù)據(jù)，4096條數(shù)據(jù)就要存3層，原因是數(shù)據(jù)放在節(jié)點上，占用了磁盤空間
如果把所有的數(shù)據(jù)都存儲在葉子結(jié)點里面，節(jié)省了空間，就成為了B+樹

B+樹
非葉子結(jié)點只存儲key，不存儲數(shù)據(jù)。所有數(shù)據(jù)都放在葉子結(jié)點中存儲。

8條數(shù)據(jù)的 B樹

8條數(shù)據(jù)的 B+ 樹


聚簇索引：innodb，數(shù)據(jù)和索引放在一起。如果不設(shè)置主鍵，innodb會選擇一個唯一鍵，如果沒有唯一鍵，innodb會生成一個6字節(jié)的rowid存儲，對用戶是不可見的。

oracle中可以看到rowid

非聚簇索引：數(shù)據(jù)和索引不放在一起，myisam

上圖中，id是索引。如果給name又加了索引，會再建立一個B+樹，葉子結(jié)點存的是關(guān)聯(lián)主鍵，而不是直接存數(shù)據(jù)。如下：

索引分幾類

按照索引的存儲來劃分：

聚簇索引：innodb
非聚簇索引：myisam

按照使用來分：

主鍵索引：主鍵所關(guān)聯(lián)的數(shù)據(jù)

唯一索引：mysql 默認會給唯一鍵添加索引

普通索引（輔助）：

• 回表：通過普通索引去樹中查找返回主鍵值，根據(jù)主鍵取索引樹查找數(shù)據(jù)。（line18）
• 覆蓋索引：執(zhí)行計劃能看到using index。不需要回表（line19）

組合索引：

• 最左匹配原則
  
• 謂詞下推、索引下推：
  
  
  
  join有幾種實現(xiàn)方式？
  
  什么時候會索引失效？
  

全文索引：
雖然提供了全文索引這種功能，但很少有人用。
檢索一般不在數(shù)據(jù)庫層面用模糊查詢like去做。搜索引擎常用Solr，ES和Lucene 信息檢索庫

驗證 mysql 默認會給唯一鍵添加索引：

show index from test查看索引，看到name已經(jīng)加了索引

---

其他

阿里一個面試題：MySQL的一個自增列，當前id為9，兩個線程同時寫，怎么保證寫入的是10和11而不是兩個10？

索引選擇性：如果age列一共100條記錄，唯一值只有10個，不建議添加索引。比如一些flag字段。
要看基數(shù)
hyperloglog算法用來計算基數(shù)，redis中使用到了這個算法。

創(chuàng)建表的時候要不要讓id自增?
要，這樣每次都是往后追加，不涉及頁分裂過程

總結(jié)

以上是生活随笔為你收集整理的MySQL索引机制：索引分类、索引的实现原理、索引的优化 - 公开课笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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