MySQL索引定義：索引（Index） 是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。 提取句子主干， 就可以得到索引的本質(zhì)： 索引是數(shù)據(jù)結(jié)構(gòu)。
大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)具體應(yīng)用場(chǎng)景：

數(shù)據(jù)庫(kù)是如何做到快速檢索的功能。
特別有意思的小例子。
 

mysql索引原理的理解和數(shù)據(jù)結(jié)構(gòu)

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

B+樹(shù)（為什么使用B+數(shù)）

• 所有數(shù)據(jù)都存儲(chǔ)在磁盤(pán)中，讀取數(shù)據(jù)由于IO問(wèn)題會(huì)讀取慢，如何加快IO速度

IO

1. 量：減少I(mǎi)O量
   *禁止使用slect ，避免增加不必要的量
2. 次數(shù)：減少I(mǎi)O次數(shù)

相關(guān)知識(shí)點(diǎn)

• 加入索引（加快查詢速度）
• 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：key、文件編號(hào)、當(dāng)前文件的offset（存在問(wèn)題：當(dāng)數(shù)據(jù)量特別大時(shí)，索引所占用的存儲(chǔ)空間也特別大。）
• 解決方法：索引的數(shù)據(jù)文件也需要持久化存儲(chǔ)到磁盤(pán)中，當(dāng)需要使用時(shí)直接讀取到內(nèi)存中，加快數(shù)據(jù)的訪問(wèn)（分而治之：分塊讀取）
• 操作系統(tǒng)基本概念：
  1.局部性原理：數(shù)據(jù)和程序都有聚集成群的傾向，之前被查詢過(guò)的數(shù)據(jù)很快會(huì)再次被查詢。冷熱數(shù)據(jù)（一級(jí)緩存，二級(jí)緩存的意思）
  2.磁盤(pán)預(yù)讀：在數(shù)據(jù)交換時(shí)，會(huì)有一個(gè)基本邏輯單位頁(yè)，一般占用空間是4k，每次在進(jìn)行數(shù)據(jù)獲取時(shí)可以獲取整頁(yè)的整數(shù)倍。（mysql中innodb的存儲(chǔ)引擎讀取數(shù)據(jù)會(huì)讀取16k show variables like ‘%innodb’）

ket-value格式數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)：

1. 哈希表
2. 樹(shù)（二叉樹(shù)、BST、AVL、紅黑樹(shù)、B樹(shù)、B+樹(shù)）
   二分支的缺點(diǎn)：深度太深，解決方法：B樹(shù)（多叉樹(shù)）

B樹(shù)

• 搜索樹(shù)
• 多節(jié)點(diǎn)多分支的數(shù)
   
  問(wèn)題：假設(shè)磁盤(pán)塊存放16條數(shù)據(jù)，如果是三層樹(shù)，最多存放的數(shù)據(jù)：161616=4096，即48k才存放4096條數(shù)據(jù)
   

B數(shù)存在問(wèn)題：存放了數(shù)據(jù)，依然占用空間，如何減少數(shù)據(jù)，需要用到B+數(shù)

B+樹(shù)

• 最下面的葉子節(jié)點(diǎn)存放的是順序全量數(shù)據(jù)
• 非葉子節(jié)點(diǎn)可以不用存放data
   
• 問(wèn)題：讀取數(shù)據(jù)，假設(shè)三層樹(shù)48k磁盤(pán)塊，1000字節(jié)為1kb，指針和鍵值占10字節(jié)，1行記錄1k 161000/10=160016001600=40960000的數(shù)據(jù)范圍，即Key鍵值，最下面的只存放一遍數(shù)據(jù)*
• 建索引時(shí)，key要盡可能少的占用空間
   

索引技術(shù)名詞

**回表：**從非聚簇索引跳轉(zhuǎn)到聚簇索引中查找數(shù)據(jù)的過(guò)程（避免回表操作select * from table ）
索引覆蓋當(dāng)非聚簇索引的葉子節(jié)點(diǎn)中包含了查詢需要的所有字段時(shí)，不需要回表的過(guò)程（推薦使用select id,name from table ）
最左匹配:、索引下推