MySQL_索引樹

查看樹插入刪除圖解：

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名注冊、網頁空間、營銷軟件、網站建設、尼元陽網站維護、網站推廣。

時間復雜度：O(N)

時間復雜度：O(logn)

如果數(shù)據(jù)插入是遞增或者遞減順序的話，會使樹成為鏈式結構。 時間復雜度：O(N)

為了保證平衡，在插入或者刪除的時候必須要旋轉，通過插入或者刪除性能的損失來彌補查詢性能的提升。

但如果寫請求和讀請求一樣多的時候怎么辦？

隨著數(shù)據(jù)的插入，樹的深度會變深，樹的深度越深，意味著 IO 次數(shù)越多。影響數(shù)據(jù)讀取的效率。

MySQL 的頁大小是16k。假設只有data 占用空間且占用 1k 一個磁盤塊可以放置16條記錄，三層就是 4096條記錄?？隙ㄐ∮?4096.

如果想要放入更多的數(shù)據(jù)的化，得加層。加層 IO 量肯定上來了。

data 太占內存，導致存儲數(shù)據(jù)太少。

MySQL加載索引是以磁盤塊（頁）為單位的，頁（Page）是 Innodb 存儲引擎用于管理數(shù)據(jù)的最小磁盤單位。默認的頁大小為 16KB。

假設只有 p1+key 值 占用空間且占用 10字節(jié)， 一個磁盤塊可以放置1600條記錄，三層就是 40960000條記錄。

在B+樹 上有兩個頭節(jié)點，一個指向根節(jié)點，另一個指向關鍵字最小的葉子節(jié)點，而且所有的葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈式環(huán)結構，因此可以對 B+樹 進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點開始，進行隨機查找。

讓當前key值盡可能的少占用存儲空間，才能保證存儲更多的值。降低樹的高度，減少IO。

保證key的長度越小越好。

徹底搞懂MySql的B+Tree

官方定義：一種能為mysql提高查詢效率的數(shù)據(jù)結構，索引是為了加速對表中數(shù)據(jù)行的檢索而創(chuàng)建的一種分散存儲的數(shù)據(jù)結構。好比如，一本書，你想找到自己想看的章節(jié)內容，直接查詢目錄就行。這里的目錄就類似索引的意思。

如上圖中，如果現(xiàn)在有一條sql語句 select * from user where id = 40，如果沒有索引的條件下，我們要找到這條記錄，我們就需要在數(shù)據(jù)中進行全表掃描，匹配id = 40的數(shù)據(jù)。

如果有了索引，我們就可以通過索引進行快速查找，如上圖中，可以先在索引中通過id = 40進行二分查找，再根據(jù)定位到的地址取出對應的行數(shù)據(jù)。

現(xiàn)在看來，索引是不是也不過如此。咋們接著往下看。

那么有的同學可能會問，既然索引缺點這么多，那我為什么還要用索引??？也就是提高了查詢速度而已。

提高了查詢速度呀，這個絕對是個大優(yōu)勢，在數(shù)據(jù)量龐大的情況下，我們通過命中索引，能大大的提高查詢速度，增刪改基本消耗忽略不計。摘抄阿里P3C開發(fā)規(guī)范。

我們先來看一個sql

執(zhí)行完后：

奇怪？為什么數(shù)據(jù)和我插入的順序不一致呢，竟然給我自動排序好了?。?！我們接著看

其實mysql每條數(shù)據(jù)的存儲是這樣子的（圖自己畫的，—_—,將就下）

mysql給我們提供了頁的概念，并且有頁目錄，頁目錄數(shù)據(jù)為葉族節(jié)點每頁的第一條數(shù)據(jù)id，頁目錄和每頁大小均默認為16KB，如下圖：

舉個例子：

那么有的小伙伴可能會問，你這樣也存不了多少數(shù)據(jù)呀，那假如我數(shù)據(jù)量非常多呢，這顆數(shù)怎么存呢。

以上表而言，一個id占用8個字節(jié)（long類型），name 20個字節(jié)，p指針也要占用字節(jié)的（大概4~8個字節(jié)），我們以最大8來算，那么一條數(shù)據(jù)大概就是：8+20+8=36，36個字節(jié)，那么一頁換算一下是 16x1024 = 16384 個字節(jié)，那么葉子節(jié)點一頁可以存儲數(shù)據(jù)量為：16384/36 = 455 條數(shù)據(jù)。那么頁目錄又存著id，一個id8個字節(jié)，能存儲16x1024/8 =2048，2048x455 = 931,840 ...粗略的算了下3層數(shù)，能存儲數(shù)據(jù)量為1,908,408,320個 很多了，可能表的字段很多的話，存儲數(shù)據(jù)量稍微少點，但是也很多了。

B+Tree是在B-Tree基礎上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結構，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結構。

這個時候有個問題思考下？為什么mysql推薦ID自增呢？這個時候是不是心里有了答案呢？或許自己可以先想想再看。

我們日常工作中，根據(jù)實際情況自行添加的索引都是輔助索引，輔助索引就是一個為了需找主鍵索引的二級索引，現(xiàn)在找到主鍵索引再通過主鍵索引找數(shù)據(jù)； （這就是所謂的回表查詢）

聚簇索引就是按照每張表的主鍵構造一顆B+樹，同時葉子節(jié)點中存放的就是整張表的行記錄數(shù)據(jù)，也將聚集索引的葉子節(jié)點稱為數(shù)據(jù)頁。這個特性決定了索引組織表中數(shù)據(jù)也是索引的一部分，每張表只能擁有一個聚簇索引。

聚簇索引并不是一種單獨的索引類型，而 是一種數(shù)據(jù)存儲方式 。具體細節(jié)依賴于其實現(xiàn)方式。

聚簇索引的優(yōu)缺點

優(yōu)點：

1.數(shù)據(jù)訪問更快，因為聚簇索引將索引和數(shù)據(jù)保存在同一個B+樹中，因此從聚簇索引中獲取數(shù)據(jù)比非聚簇索引更快

2.聚簇索引對于主鍵的排序查找和范圍查找速度非?？? 缺點：

1.插入速度嚴重依賴于插入順序，按照主鍵的 順序插入 是最快的方式，否則將會出現(xiàn)頁分裂，嚴重影響性能。因此，對于InnoDB表，我們一般都會定義一個 自增的ID列為主鍵 2. 更新主鍵的代價很高 ，因為將會導致被更新的行移動。因此，對于InnoDB表，我們一般定義主鍵為不可更新。 3.二級索引訪問需要兩次索引查找，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)。

在 聚簇索引之上創(chuàng)建的索引稱之為輔助索引 ，輔助索引訪問數(shù)據(jù)總是需要二次查找。輔助索引葉子節(jié)點存儲的不再是行的物理位置，而是主鍵值。通過輔助索引首先找到的是主鍵值，再通過主鍵值找到數(shù)據(jù)行的數(shù)據(jù)頁，再通過數(shù)據(jù)頁中的Page Directory找到數(shù)據(jù)行。

--以上可能沒有說完整，或者有遺漏的地方，歡迎補充?。?！

mysql如何創(chuàng)建二叉樹

在二叉樹中有一種平衡二叉樹，通過平衡算法可以讓二叉樹兩邊的節(jié)點平均分布，這樣就能讓所有的索引查找都在一個近似的時間內完成。而MySQL這類數(shù)據(jù)庫采用了二叉樹的升級版B+Tree的形式，每個節(jié)點有三個支葉，不過其算法原理仍然是平衡樹的原理。