二叉樹
- 對半搜尋，每個節點最多兩個孩子
- 左側孩子小于根節點，右側孩子大于等于根節點
- 二叉排序樹的查找性能在0(Log2n)到O(n)之間
正常情況下長這樣
極端情況下長這樣
如果長這樣的，查找時間複雜度就是O(n)了，那麼就得靠平衡二叉樹優化了，現在有請平衡二叉樹登場…
平衡二叉樹
- 滿足二叉樹
- 任何節點的兩個子樹的高度最大差為1
- 如果對平衡二叉樹進行删除和新增，那麼會破壞平衡，就會出發旋轉，最終達到平衡，也成自平衡二叉樹
雖然能做到平衡了，避免了O(n)，但是每次都進行頻繁的左旋或右旋，咱也扛不住啊，是以來試試紅黑樹
紅黑樹
- 也是自平衡（但沒有高度差為1的限制，它有另外一套規則）
- 每個結點是紅的或者黑的
- 根結點是黑的
- 每個葉子結點是黑的（NULL）
- 樹中不存在兩個相鄰的紅色結點（即紅色結點的父結點和孩子結點均不能是紅色）
- 從根結點到其任何後代 NULL 結點（預設是黑色的）的每條路徑都具有相同數量的黑色結點。
這一點比較難懂：從任意一個結點（包括根結點）到其任何後代 NULL 結點（預設是黑色的）的每條路徑都具有相同數量的黑色結點。沒聽懂？
解釋下：這裡每個葉子結點（2，4，6，55）都有一個黑色的NULL節點，那麼從根節點003到任意的null節點都會經過相同個數的黑色節點（包括黑色的null節點），這樣懂了吧。
Hash
- 對索引的key進行一次hash計算就可以定位出資料存儲的位置
- 很多時候Hash索引要比B+ 樹索引更高效
- 僅能滿足 “=”，“IN”，不支援範圍查詢
- hash沖突問題
B-Tree
- 葉節點具有相同的深度，葉節點的指針為空；
- 所有索引元素不重複；
- 節點中的資料索引從左到右遞增排列；
- 資料節點存在每個節點上
B+ -Tree
- 非葉子節點不存儲data，隻存儲索引(備援)，可以放更多的索引
- 葉子節點包含所有索引字段
- 葉子節點用雙向指針連接配接，提高區間通路的性能