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

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

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

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

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

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

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

IO

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

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

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

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

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

B樹

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

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

B+樹

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

索引技術(shù)名詞

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