b站講的好的視訊
B樹講的比較好的部落格
1、B-樹 簡介
B-樹，也稱為B樹，是一種平衡的多叉樹（可以對比一下平衡二叉查找樹），它比較适用于對外查找。
- 階數：一個節點最多有多少個孩子節點。（一般用字母m表示）
- 關鍵字：節點上的數值就是關鍵字
- 度：一個節點擁有的子節點的數量。
一顆m階的B-樹，有以下特征：
- 根結點至少有兩個子女；
- 每個非根節點所包含的關鍵字個數 j 滿足：m/2 - 1 <= j <= m - 1.(表示向上取整)
- 有k個關鍵字(關鍵字按遞增次序排列)的非葉結點恰好有k+1個孩子。
- 所有的葉子結點都位于同一層。
一棵簡單的B-樹如下：
2、B+ 樹簡介
B+樹是B-樹的變體，也是一顆多路搜尋樹。一棵m階的B+樹主要有這些特點：
- 每個結點至多有m個子女;
- 非根節點關鍵值個數範圍：m/2 <= k <= m-1
- 相鄰葉子節點是通過指針連起來的，并且是關鍵字大小排序的。
一顆3階的B+樹如下：
B+樹和B-樹的主要差別如下：
- B-樹内部節點是儲存資料的;而B+樹内部節點是不儲存資料的，隻作索引作用，它的葉子節點才儲存資料。是以在相同的資料量下，B+樹更加矮壯。
- B+樹相鄰的葉子節點之間是通過連結清單指針連起來的，友善于周遊查詢（周遊操作在MySQL中比較常見），而B-樹卻不是。
- 查找過程中，B-樹在找到具體的數值以後就結束，而B+樹則需要通過索引找到葉子結點中的資料才結束
- B-樹中任何一個關鍵字出現且隻出現在一個結點中，而B+樹可以出現多次。
- B樹是會在非葉子節點也存儲資料，要周遊的時候可能就得跨層檢索，相對麻煩些。
B+樹與紅黑樹差別：
- MySQL的資料是存儲在硬碟的，在查詢時一般是不能「一次性」把全部資料加載到記憶體中，而紅黑樹是「二叉查找樹」的變種，一個Node節點隻能存儲一個Key和一個Value。
- B和B+樹跟紅黑樹不一樣，它們算是「多路搜尋樹」，相較于「二叉搜尋樹」而言，一個Node節點可以存儲的資訊會更多，「多路搜尋樹」的高度會比「二叉搜尋樹」更低。
- 了解了差別之後，其實就很容易發現，在資料不能一次加載至記憶體的場景下，資料需要被檢索出來，選擇B或B+樹的理由就很充分了（一個Node節點存儲資訊更多（相較于二叉搜尋樹），樹的高度更低，樹的高度影響檢索的速度）
B+樹與哈希表差別：
- 哈希索引能以 O(1) 時間進行查找，但是失去了有序性。無法用于排序與分組、隻支援精确查找，無法用于部分查找和範圍查找。
- InnoDB 存儲引擎有一個特殊的功能叫“自适應哈希索引”，當某個索引值被使用的非常頻繁時，會在 B+ 樹索引之上再建立一個哈希索引，這樣就讓 B+Tree 索引具有哈希索引的一些優點，比如：快速的哈希查找。
B+樹的插入：
- B+樹插入都是在葉子結點進行的，就是插入前，需要先找到要插入的葉子結點。
- 如果被插入關鍵字的葉子節點，目前含有的關鍵字數量是小于階數m，則直接插入。
- 如果插入關鍵字後，葉子節點目前含有的關鍵字數目等于階數m，則插，該節點開始 「分裂」為兩個新的節點，一個節點包含m/2 個關鍵字，另外一個關鍵字包含m/2個關鍵值。（m/2表示向下取整，m/2表示向上取整，如3/2=2）。
- 分裂後，需要将第m/2的關鍵字上移到父結點。如果這時候父結點中包含的關鍵字個數小于m，則插入操作完成。
- 分裂後，需要将m/2的關鍵字上移到父結點。如果父結點中包含的關鍵字個數等于m，則繼續分裂父結點。
3、查找
在一個頁中查找：
- 以主鍵為搜尋條件：在頁目錄中使用二分法快速定位到對應的槽；然後周遊該槽對應分組中的記錄，即可快速找到指定的記錄。
- 以其他列作為搜尋條件：從Infimum記錄開始依次周遊單向連結清單中的每條記錄，然後對比每條記錄是否複合搜尋條件。
在很多頁中查找：
- 定位到記錄所在頁；
- 從所在的頁内查找相應的記錄。
如果沒有索引，就要周遊每一頁，再周遊每組記錄。
4、InnoDB與MyISAM差別
- InnoDB 支援事務，MyISAM 不支援事務。這是 MySQL 将預設存儲引擎從 MyISAM 變成 InnoDB 的重要原因之一；
- InnoDB 支援外鍵，而 MyISAM 不支援。對一個包含外鍵的 InnoDB 表轉為 MYISAM 會失敗；
- InnoDB 是聚集索引，MyISAM 是非聚集索引。聚簇索引的檔案存放在主鍵索引的葉子節點上，是以 InnoDB 必須要有主鍵，通過主鍵索引效率很高。但是輔助索引需要兩次查詢，先查詢到主鍵，然後再通過主鍵查詢到資料。是以，主鍵不應該過大，因為主鍵太大，其他索引也都會很大。而 MyISAM 是非聚集索引，資料檔案是分離的，索引儲存的是資料檔案的指針。主鍵索引和輔助索引是獨立的。
- InnoDB 不儲存表的具體行數，執行 select count(*) from table 時需要全表掃描。而MyISAM 用一個變量儲存了整個表的行數，執行上述語句時隻需要讀出該變量即可，速度很快；
- InnoDB 最小的鎖粒度是行鎖，MyISAM 最小的鎖粒度是表鎖。一個更新語句會鎖住整張表，導緻其他查詢和更新都會被阻塞，是以并發通路受限。這也是 MySQL 将預設存儲引擎從 MyISAM 變成 InnoDB 的重要原因之一；
- MyISAM存儲引擎的資料和索引分開存儲，這種存儲引擎的索引全部都是二級索引，在葉子節點處存儲的是列+行号（對于定長記錄格式的記錄來說）。
5、搜尋區間
- In操作符的語義與若幹個等值比對操作符（=）之間用OR連接配接起來的語義是一樣的，都會産生多個單點掃描區間。如：
where key2 in (1434, 6328)
where key2 = 1434 or key2 = 6328
- !=産生的掃描區間是（-無窮，a），（a，+無窮）；
- like操作符比較特殊，隻有在比對完整的字元串或者比對字元串字首時才産生合适掃描區間。
6、建立和使用索引時注意事項
- 隻為用于搜尋、排序或分組的列建立索引；
- 當列中不重複的值的個數在總記錄條數中的占比很大時，才為列建立索引；
- 索引列的類型盡量小；
- 可以隻為索引列字首建立索引，以減少索引占用的存儲空間；
- 盡量使用覆寫索引進行查詢，以避免回表操作帶來的性能損耗；
- 讓索引列以列名的形式單獨出現在搜尋條件中；
- 為了盡可能少的讓聚簇索引發生頁面分裂的情況，建議讓主鍵擁有自增屬性；
- 定位并删除表中的備援和重複索引。