二叉查找樹
1.為什麼會出現二叉查找樹？
二分法可以很好的對有序數組進行查找，但增删比較低效
連結清單可以很好的增删元素，查找低效，且使用二分法也低效
------> 出現了普通二叉查找樹的資料結構
特征：左子樹所有節點 < 根節點 < 右子樹所有節點
中序周遊是有序的
查找的時間複雜度：O(logN)
2.普通二叉查找樹缺點？
3.如果每次節點插入都能自動平衡，那麼會保持二叉查找樹的性能，該如何設計呢？
-----> 于是有了AVL樹
AVL樹
有二叉查找樹的所有特征
每個節點的左子樹和右子樹的高度差最多等于1
4.AVL樹的缺點？
解決了二叉查找樹退化成連結清單的缺點，将時間負責度控制在O(logN)
平衡樹的要求太高了：左右子樹高度差最多為1，導緻每次插入/删除節點的時候幾乎都需要通過左旋或者右旋來進行調整
在頻繁插入、删除的場景中，平衡樹會頻繁調整，大大降低性能
5.為了解決AVL樹的缺點，于是出現了紅黑樹，為什麼紅黑樹可以解決AVL樹的缺點？
右旋：
原理&手寫紅黑樹：https://www.bilibili.com/video/BV1UJ411J7CU?p=4
6.紅黑樹使用場景？
Java8之後的hashmaphash沖突的解決方案資料結構
廣泛用在C++的STL中，如map和set都是用紅黑樹實作的
7.與字典樹的差別？
字典樹（trie樹）用在統計和排序大量字元串，如自動機。
8.相似的資料結構？
B樹：與平衡二叉樹相似，不同的是B樹屬于多叉樹，又名 平衡多路查找樹
B-樹：多路搜尋樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字範圍的子結點；
所有關鍵字在整顆樹中出現，且隻出現一次，非葉子結點可以命中；
B+樹：在B-樹基礎上，為葉子結點增加連結清單指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
B*樹：在B+樹基礎上，為非葉子結點也增加連結清單指針，将結點的最低使用率從1/2提高到2/3；
B樹相對于紅黑樹的差別？
在大規模資料存儲的時候，紅黑樹往往出現由于樹的深度過大而造成磁盤IO讀寫過于頻繁，進而導緻效率低下的情況。為什麼會出現這樣的情況，我們知道要擷取磁盤上資料，必須先通過磁盤移動臂移動到資料所在的柱面，然後找到指定盤面，接着旋轉盤面找到資料所在的磁道，最後對資料進行讀寫。磁盤IO代價主要花費在查找所需的柱面上，樹的深度過大會造成磁盤IO頻繁讀寫。根據磁盤查找存取的次數往往由樹的高度所決定，是以，隻要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度，B樹可以有多個子女，從幾十到上千，可以降低樹的高度。
B樹和B+樹的差別？
B樹所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字資訊。
B+樹所有的葉子結點中包含了全部關鍵字的資訊，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序連結，所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (而B 樹的非終節點也包含需要查找的有效資訊)
為什麼說B+比B樹更适合實際應用中作業系統的檔案索引和資料庫索引？
1) B+的磁盤讀寫代價更低
B+的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
2) B+-tree的查詢效率更加穩定
由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。
資料庫索引采用B+樹的主要原因是 B樹在提高了磁盤IO性能的同時并沒有解決元素周遊的效率低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹隻要周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的，而B樹不支援這樣的操作（或者說效率太低）
9.用途？
B樹是為了提高磁盤或外部儲存設備查找效率而産生的一種多路平衡查找樹。
B+樹為B樹的變形結構，用于大多數資料庫或檔案系統的存儲而設計。