㈠ 數據結構和演算法優化
APP的優化是任重而道遠的過程，必須在意每一個環節，否者當你想要優化的時候，發現到處都是坑，已經不知道填補哪裡了，所以我們必須一點一滴的做起。
數據結構和演算法優化
能帶來什麼好處呢？他能使得你程序獲得數據更快，內存佔用更合理。最終體現為響應快內存佔用小。
我們先看常見的數據結構類型特點
數組 ： 一片物理上連續的大小確定的儲存空間 。int[num]
順序表 ：物理上連續、邏輯上連續、大小可以動態增加。ArrayList （查找快，添加刪除慢）
鏈表 ：物理上不連續、邏輯上連續、可以動態增加和刪除節點。LinkedList （查找慢只能輪尋，增加刪除快）
物理上連續：數組或者鏈表在初始化的時候，會申請分配內存空間：只要存儲空間足夠你申請的大小就分配給你初始化（物理不連續）；必須要連續的存儲空間，我才給你分配，否則失敗（物理上連續）
那麼有沒有繼承純虛標和鏈表的2個有點的數據結構呢？HashMap！
HashMap
它是由數組和鏈表結合組成。（HashMap：JDK1.7之前 24 之前： 數組+ 鏈表； HashMap：JDK1.8 之後： 數組+ 鏈表 + 紅黑樹）
下面是HashMap結構圖
它是怎麼操作的呢？為什麼他能同時擁有順序表和鏈表的優點呢？ 搞清它的實現方式，我們就可以知道了， 大致可以分為以下的步驟。
①put方法，傳入object和value，通過hash運算得到一個int類型的hashcode，這里假設為X（後續X為這個hashcode）。
②hashmap內部是有一個table數組+鏈表形成的。我們拿到這個X後，使用X/table.length(hashcode值/table[].length),得到一個小於table.length的值M，該值就是這個value應該放置的數組位置。我們准備把value放入table[M]中。
③我們把hashcode和value打包為一個node節點(為什麼需要這么打包後續會提到),准備存入table[M]中。
④出入table數組的鏈表中有2種方式：
前插方式：不管數組table[M]節點有值與否，都把這個准備插入的node節點作為數組的根節點。可能出現2種情況：
（1）如果table[M]節點沒有值，則node節點作為數組的根節點。
（2）如果table[M]節點已存在數據鏈表，就把這些數據鏈表，鏈到這個准備插入的node節點上，以弄得節點為根節點放入table[M中]。
後插方式：可能會出現的2種情況
(1) 如果table[M]節點沒有值，則node節點作為數組的根節點。
（2）如果table[M]節點已存在數據鏈表，則把node節點鏈到該數據鏈表的最後一個節點上。
經歷以上4個步驟就完成了hashmap的插入操作，現在解釋一下為什麼要打包為node節點。
舉個栗子，假如hashmap.length=16,我們准備存入ObjectA(OA)和ObjectB(OB),假設OA經過hash運算得到的hashcode是1，OB經過hash運算得到hashcode是17，OA和OB進行求模運算結果都為1，鏈到鏈表上時，我們get方法的時候怎麼取到正確的值呢，因為鏈表上的模運算都是1.這個時候我們就需要通過hashcode來識別這個鏈表上的哪個值是OA的value哪個是OB的value，因為我們已經把hashcode和value打包起來了。
補充
hashmap的table數組的大小事是2的次冪（不要問為什麼，源碼定的，他們肯定經過大量的統計或者運算，這是科學）。table數組默認的長度是16，也就是說你new一個空的hashmap長度為16，當然也提供了一個給你設置長度的方法，但是假如你設置17，則長度會為32，這不難理解。
hash碰撞
hash碰撞就是，假如OA、OB...ON經過模運算得到的數組位置相同，那麼他們都會掛在這個數組節點的鏈表上，極端情況想整個hashmap看起來像單鏈表。但這種情況這並不是我們想要的結果。我們可以通過擴容來盡可能的避免hash碰撞。
擴容 ：（意義，在於避免大量的hash碰撞，因為在某些極端情況下，有點像單鏈表）
閾值 ：閾值=table.length* DEFAULT_LOAD_FACTOR （擴容系數，默認為0.75，也可以自己設定，一般不做修改）
hashmap定義：當hashmap中的元素個數超過閾值大小時，我們就需要對table數組進行2倍擴容，如從16→32。
注意：擴容後hashmap會調用resize()，對hashmap內的數據重新計算所有元素的位置 。 。因為假如你之前17/16=1，現在17/32=17，你的位置發生變化了。
缺點 ：
hashMap因為有閾值的擴容機制，所以一定會有空間浪費，比如0.75的時候，一定有25%空間被浪費掉了。空間換時間。
hashmap是線程不安全的。因為可能在一個線程擴容（resize（）方法執行）的情況下,另外一個線程在get，但是拿不到之前的數據了，因為擴容。所以是線程不安全的。或者線程擴容（resize（）方法執行時，多線程進行put的時候導致的多線程數據不一致。
如何線程安全的使用HashMap?使用使用鎖分段技術或者使用HashTable(Hashtable的方法是Synchronize的，而HashMap不是,其實也就是鎖機制起作用)。
SparseArray（Android為了優化內存所提供的api）
特性：key為int,value為object，二分查找的思想，雙數組，刪除的時候節點不刪除，而是把value刪除，避免刪除的時候數組還要移動。
SparseArray比HashMap更省內存，在某些條件下性能更好，主要是因為它避免了對key的自動裝箱（int轉為Integer類型），它內部則是通過兩個數組來進行數據存儲的，一個存儲key，另外一個存儲value，為了優化性能，它內部對數據還採取了壓縮的方式來表示稀疏數組的數據，從而節約內存空間，我們從源碼中可以看到key和value分別是用數組表示。
為什麼是能夠進行二分查找呢？從源碼上看key和value分別是用int類型數組和object數組表示，所以這也是SparseArray的局限性。
private int[] mKeys;
private Object[] mValues;
為什麼說SparseArray比HashMap更省內存，在某些條件下性能更好？
因為SparseArray有以下一個特性，首先它是2個數組，在數據查找的時候無疑會比hashmap快很多，其次在刪除的時候，SparseArray並不會把數組key位置進行刪除，而是把key的索引value置位DELETE標志（這樣就避免了數組delete操作後的array的操作）。當我們下次進行插入的時候，若要插入的位置key的索引value為DELETE標志，則把數據覆蓋給value（只是經歷了set操作，並無其他操作）。否則進行add操作（包含array）。
所以經過以上的情況，我們可以看出，SparseArray相對於HashMap,會越用越快。
缺點
（1）SparseArray僅僅能存儲key為int類型的數據。
（2）插入操作需要復制數組，增刪效率降低 數據量巨大時，復制數組成本巨大，gc()成本也巨大。
（3）數據量巨大時，查詢效率也會明顯下降。
（4）線程不安全問題，類似hashmap
一般我們在滿足下面兩個條件我們可以使用SparseArray代替HashMap：
（1）數據量不大，最好在千級以內
（2）key必須為int類型，這中情況下的HashMap可以用SparseArray代替：
ArrayMap（Android為了優化內存所提供的api）
ArrayMap和SparseArray差不多，不同的是key類型可以是object類型。
ArrayMap的2個數組，一個數組記錄key的hash值，另外一個數組記錄Value值。其他存儲方式和運行思想和SparseArray一致。
線程不安全:hashmap、ArrayMap、SparseArray
㈡ 紅黑樹和平衡二叉樹 區別
紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(2)紅黑樹存儲優化擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹
㈢ 如何提高Linux下塊設備IO的整體性能
前言：本文主要講解Linux IO調度層的三種模式：cfp、deadline和noop，並給出各自的優化和適用場景建議。
IO調度發生在Linux內核的IO調度層。這個層次是針對Linux的整體IO層次體系來說的。從read()或者write()系統調用的角度來說，Linux整體IO體系可以分為七層，它們分別是：
VFS層： 虛擬文件系統層。由於內核要跟多種文件系統打交道，而每一種文件系統所實現的數據結構和相關方法都可能不盡相同，所以，內核抽象了這一層，專門用來適配各種文件系統，並對外提供統一操作介面。
文件系統層： 不同的文件系統實現自己的操作過程，提供自己特有的特徵，具體不多說了，大家願意的話自己去看代碼即可。
頁緩存層： 負責真對page的緩存。
通用塊層： 由於絕大多數情況的io操作是跟塊設備打交道，所以Linux在此提供了一個類似vfs層的塊設備操作抽象層。下層對接各種不同屬性的塊設備，對上提供統一的Block IO請求標准。
IO調度層 ：因為絕大多數的塊設備都是類似磁碟這樣的設備，所以有必要根據這類設備的特點以及應用的不同特點來設置一些不同的調度演算法和隊列。以便在不同的應用環境下有針對性的提高磁碟的讀寫效率，這里就是大名鼎鼎的Linux電梯所起作用的地方。針對機械硬碟的各種調度方法就是在這實現的。
塊設備驅動層： 驅動層對外提供相對比較高級的設備操作介面，往往是C語言的，而下層對接設備本身的操作方法和規范。
塊設備層： 這層就是具體的物理設備了，定義了各種真對設備操作方法和規范。
有一個已經整理好的[Linux IO結構圖]，非常經典，一圖勝千言：
我們今天要研究的內容主要在IO調度這一層。
它要解決的核心問題是，如何提高塊設備IO的整體性能？這一層也主要是針對機械硬碟結構而設計的。
眾所周知，機械硬碟的存儲介質是磁碟，磁頭在碟片上移動進行磁軌定址，行為類似播放一張唱片。
這種結構的特點是，順序訪問時吞吐量較高，但是如果一旦對碟片有隨機訪問，那麼大量的時間都會浪費在磁頭的移動上，這時候就會導致每次IO的響應時間變長，極大的降低IO的響應速度。
磁頭在碟片上尋道的操作，類似電梯調度，實際上在最開始的時期，Linux把這個演算法命名為Linux電梯演算法，即：
如果在尋道的過程中，能把順序路過的相關磁軌的數據請求都「順便」處理掉，那麼就可以在比較小影響響應速度的前提下，提高整體IO的吞吐量。
這就是我們為什麼要設計IO調度演算法的原因。
目前在內核中默認開啟了三種演算法/模式：noop，cfq和deadline。嚴格算應該是兩種：
因為第一種叫做noop，就是空操作調度演算法，也就是沒有任何調度操作，並不對io請求進行排序，僅僅做適當的io合並的一個fifo隊列。
目前內核中默認的調度演算法應該是cfq，叫做完全公平隊列調度。這個調度演算法人如其名，它試圖給所有進程提供一個完全公平的IO操作環境。
註：請大家一定記住這個詞語，cfq，完全公平隊列調度，不然下文就沒法看了。
cfq為每個進程創建一個同步IO調度隊列，並默認以時間片和請求數限定的方式分配IO資源，以此保證每個進程的IO資源佔用是公平的，cfq還實現了針對進程級別的優先順序調度，這個我們後面會詳細解釋。
查看和修改IO調度演算法的方法是：
cfq是通用伺服器比較好的IO調度演算法選擇，對桌面用戶也是比較好的選擇。
但是對於很多IO壓力較大的場景就並不是很適應，尤其是IO壓力集中在某些進程上的場景。
因為這種場景我們需要更多的滿足某個或者某幾個進程的IO響應速度，而不是讓所有的進程公平的使用IO，比如資料庫應用。
deadline調度（最終期限調度）就是更適合上述場景的解決方案。deadline實現了四個隊列：
其中兩個分別處理正常read和write，按扇區號排序，進行正常io的合並處理以提高吞吐量。因為IO請求可能會集中在某些磁碟位置，這樣會導致新來的請求一直被合並，可能會有其他磁碟位置的io請求被餓死。
另外兩個處理超時read和write的隊列，按請求創建時間排序，如果有超時的請求出現，就放進這兩個隊列，調度演算法保證超時（達到最終期限時間）的隊列中的請求會優先被處理，防止請求被餓死。
不久前，內核還是默認標配四種演算法，還有一種叫做as的演算法（Anticipatory scheler），預測調度演算法。一個高大上的名字，搞得我一度認為Linux內核都會算命了。
結果發現，無非是在基於deadline演算法做io調度的之前等一小會時間，如果這段時間內有可以合並的io請求到來，就可以合並處理，提高deadline調度的在順序讀寫情況下的數據吞吐量。
其實這根本不是啥預測，我覺得不如叫撞大運調度演算法，當然這種策略在某些特定場景差效果不錯。
但是在大多數場景下，這個調度不僅沒有提高吞吐量，還降低了響應速度，所以內核乾脆把它從默認配置里刪除了。畢竟Linux的宗旨是實用，而我們也就不再這個調度演算法上多費口舌了。
1、cfq：完全公平隊列調度
cfq是內核默認選擇的IO調度隊列，它在桌面應用場景以及大多數常見應用場景下都是很好的選擇。
如何實現一個所謂的完全公平隊列（Completely Fair Queueing）？
首先我們要理解所謂的公平是對誰的公平？從操作系統的角度來說，產生操作行為的主體都是進程，所以這里的公平是針對每個進程而言的，我們要試圖讓進程可以公平的佔用IO資源。
那麼如何讓進程公平的佔用IO資源？我們需要先理解什麼是IO資源。當我們衡量一個IO資源的時候，一般喜歡用的是兩個單位，一個是數據讀寫的帶寬，另一個是數據讀寫的IOPS。
帶寬就是以時間為單位的讀寫數據量，比如，100Mbyte/s。而IOPS是以時間為單位的讀寫次數。在不同的讀寫情境下，這兩個單位的表現可能不一樣，但是可以確定的是，兩個單位的任何一個達到了性能上限，都會成為IO的瓶頸。
從機械硬碟的結構考慮，如果讀寫是順序讀寫，那麼IO的表現是可以通過比較少的IOPS達到較大的帶寬，因為可以合並很多IO，也可以通過預讀等方式加速數據讀取效率。
當IO的表現是偏向於隨機讀寫的時候，那麼IOPS就會變得更大，IO的請求的合並可能性下降，當每次io請求數據越少的時候，帶寬表現就會越低。
從這里我們可以理解，針對進程的IO資源的主要表現形式有兩個： 進程在單位時間內提交的IO請求個數和進程佔用IO的帶寬。
其實無論哪個，都是跟進程分配的IO處理時間長度緊密相關的。
有時業務可以在較少IOPS的情況下佔用較大帶寬，另外一些則可能在較大IOPS的情況下佔用較少帶寬，所以對進程佔用IO的時間進行調度才是相對最公平的。
即，我不管你是IOPS高還是帶寬佔用高，到了時間咱就換下一個進程處理，你愛咋樣咋樣。
所以，cfq就是試圖給所有進程分配等同的塊設備使用的時間片，進程在時間片內，可以將產生的IO請求提交給塊設備進行處理，時間片結束，進程的請求將排進它自己的隊列，等待下次調度的時候進行處理。這就是cfq的基本原理。
當然，現實生活中不可能有真正的「公平」，常見的應用場景下，我們很肯能需要人為的對進程的IO佔用進行人為指定優先順序，這就像對進程的CPU佔用設置優先順序的概念一樣。
所以，除了針對時間片進行公平隊列調度外，cfq還提供了優先順序支持。每個進程都可以設置一個IO優先順序，cfq會根據這個優先順序的設置情況作為調度時的重要參考因素。
優先順序首先分成三大類：RT、BE、IDLE，它們分別是實時（Real Time）、最佳效果（Best Try）和閑置（Idle）三個類別，對每個類別的IO，cfq都使用不同的策略進行處理。另外，RT和BE類別中，分別又再劃分了8個子優先順序實現更細節的QOS需求，而IDLE只有一個子優先順序。
另外，我們都知道內核默認對存儲的讀寫都是經過緩存（buffer/cache）的，在這種情況下，cfq是無法區分當前處理的請求是來自哪一個進程的。
只有在進程使用同步方式（sync read或者sync wirte）或者直接IO（Direct IO）方式進行讀寫的時候，cfq才能區分出IO請求來自哪個進程。
所以，除了針對每個進程實現的IO隊列以外，還實現了一個公共的隊列用來處理非同步請求。
當前內核已經實現了針對IO資源的cgroup資源隔離，所以在以上體系的基礎上，cfq也實現了針對cgroup的調度支持。
總的來說，cfq用了一系列的數據結構實現了以上所有復雜功能的支持，大家可以通過源代碼看到其相關實現，文件在源代碼目錄下的block/cfq-iosched.c。
1.1 cfq設計原理
在此，我們對整體數據結構做一個簡要描述：首先，cfq通過一個叫做cfq_data的數據結構維護了整個調度器流程。在一個支持了cgroup功能的cfq中，全部進程被分成了若干個contral group進行管理。
每個cgroup在cfq中都有一個cfq_group的結構進行描述，所有的cgroup都被作為一個調度對象放進一個紅黑樹中，並以vdisktime為key進行排序。
vdisktime這個時間紀錄的是當前cgroup所佔用的io時間，每次對cgroup進行調度時，總是通過紅黑樹選擇當前vdisktime時間最少的cgroup進行處理，以保證所有cgroups之間的IO資源佔用「公平」。
當然我們知道，cgroup是可以對blkio進行資源比例分配的，其作用原理就是，分配比例大的cgroup佔用vdisktime時間增長較慢，分配比例小的vdisktime時間增長較快，快慢與分配比例成正比。
這樣就做到了不同的cgroup分配的IO比例不一樣，並且在cfq的角度看來依然是「公平「的。
選擇好了需要處理的cgroup（cfq_group）之後，調度器需要決策選擇下一步的service_tree。
service_tree這個數據結構對應的都是一系列的紅黑樹，主要目的是用來實現請求優先順序分類的，就是RT、BE、IDLE的分類。每一個cfq_group都維護了7個service_trees，其定義如下：
其中service_tree_idle就是用來給IDLE類型的請求進行排隊用的紅黑樹。
而上面二維數組，首先第一個維度針對RT和BE分別各實現了一個數組，每一個數組中都維護了三個紅黑樹，分別對應三種不同子類型的請求，分別是：SYNC、SYNC_NOIDLE以及ASYNC。
我們可以認為SYNC相當於SYNC_IDLE並與SYNC_NOIDLE對應。idling是cfq在設計上為了盡量合並連續的IO請求以達到提高吞吐量的目的而加入的機制，我們可以理解為是一種「空轉」等待機制。
空轉是指，當一個隊列處理一個請求結束後，會在發生調度之前空等一小會時間，如果下一個請求到來，則可以減少磁頭定址，繼續處理順序的IO請求。
為了實現這個功能，cfq在service_tree這層數據結構這實現了SYNC隊列，如果請求是同步順序請求，就入隊這個service tree，如果請求是同步隨機請求，則入隊SYNC_NOIDLE隊列，以判斷下一個請求是否是順序請求。
所有的非同步寫操作請求將入隊ASYNC的service tree，並且針對這個隊列沒有空轉等待機制。
此外，cfq還對SSD這樣的硬碟有特殊調整，當cfq發現存儲設備是一個ssd硬碟這樣的隊列深度更大的設備時，所有針對單獨隊列的空轉都將不生效，所有的IO請求都將入隊SYNC_NOIDLE這個service tree。
每一個service tree都對應了若干個cfq_queue隊列，每個cfq_queue隊列對應一個進程，這個我們後續再詳細說明。
cfq_group還維護了一個在cgroup內部所有進程公用的非同步IO請求隊列，其結構如下：
非同步請求也分成了RT、BE、IDLE這三類進行處理，每一類對應一個cfq_queue進行排隊。
BE和RT也實現了優先順序的支持，每一個類型有IOPRIO_BE_NR這么多個優先順序，這個值定義為8，數組下標為0-7。
我們目前分析的內核代碼版本為Linux 4.4，可以看出，從cfq的角度來說，已經可以實現非同步IO的cgroup支持了，我們需要定義一下這里所謂非同步IO的含義，它僅僅表示從內存的buffer/cache中的數據同步到硬碟的IO請求，而不是aio(man 7 aio)或者linux的native非同步io以及lio機制，實際上這些所謂的「非同步」IO機制，在內核中都是同步實現的（本質上馮諾伊曼計算機沒有真正的「非同步」機制）。
我們在上面已經說明過，由於進程正常情況下都是將數據先寫入buffer/cache，所以這種非同步IO都是統一由cfq_group中的async請求隊列處理的。
那麼為什麼在上面的service_tree中還要實現和一個ASYNC的類型呢？
這當然是為了支持區分進程的非同步IO並使之可以「完全公平」做准備嘍。
實際上在最新的cgroup v2的blkio體系中，內核已經支持了針對buffer IO的cgroup限速支持，而以上這些可能容易混淆的一堆類型，都是在新的體系下需要用到的類型標記。
新體系的復雜度更高了，功能也更加強大，但是大家先不要著急，正式的cgroup v2體系，在Linux 4.5發布的時候會正式跟大家見面。
我們繼續選擇service_tree的過程，三種優先順序類型的service_tree的選擇就是根據類型的優先順序來做選擇的，RT優先順序最高，BE其次，IDLE最低。就是說，RT里有，就會一直處理RT，RT沒了再處理BE。
每個service_tree對應一個元素為cfq_queue排隊的紅黑樹，而每個cfq_queue就是內核為進程（線程）創建的請求隊列。
每一個cfq_queue都會維護一個rb_key的變數，這個變數實際上就是這個隊列的IO服務時間（service time）。
這里還是通過紅黑樹找到service time時間最短的那個cfq_queue進行服務，以保證「完全公平」。
選擇好了cfq_queue之後，就要開始處理這個隊列里的IO請求了。這里的調度方式基本跟deadline類似。
cfq_queue會對進入隊列的每一個請求進行兩次入隊，一個放進fifo中，另一個放進按訪問扇區順序作為key的紅黑樹中。
默認從紅黑樹中取請求進行處理，當請求的延時時間達到deadline時，就從紅黑樹中取等待時間最長的進行處理，以保證請求不被餓死。
這就是整個cfq的調度流程，當然其中還有很多細枝末節沒有交代，比如合並處理以及順序處理等等。
1.2 cfq的參數調整
理解整個調度流程有助於我們決策如何調整cfq的相關參數。所有cfq的可調參數都可以在/sys/class/block/sda/queue/iosched/目錄下找到，當然，在你的系統上，請將sda替換為相應的磁碟名稱。我們來看一下都有什麼：
這些參數部分是跟機械硬碟磁頭尋道方式有關的，如果其說明你看不懂，請先補充相關知識：
back_seek_max:磁頭可以向後定址的最大范圍，默認值為16M。
back_seek_penalty:向後定址的懲罰系數。這個值是跟向前定址進行比較的。
以上兩個是為了防止磁頭尋道發生抖動而導致定址過慢而設置的。基本思路是這樣，一個io請求到來的時候，cfq會根據其定址位置預估一下其磁頭尋道成本。
設置一個最大值back_seek_max，對於請求所訪問的扇區號在磁頭後方的請求，只要定址范圍沒有超過這個值，cfq會像向前定址的請求一樣處理它。
再設置一個評估成本的系數back_seek_penalty，相對於磁頭向前定址，向後定址的距離為1/2(1/back_seek_penalty)時，cfq認為這兩個請求定址的代價是相同。
這兩個參數實際上是cfq判斷請求合並處理的條件限制，凡事復合這個條件的請求，都會盡量在本次請求處理的時候一起合並處理。
fifo_expire_async:設置非同步請求的超時時間。
同步請求和非同步請求是區分不同隊列處理的，cfq在調度的時候一般情況都會優先處理同步請求，之後再處理非同步請求，除非非同步請求符合上述合並處理的條件限制范圍內。
當本進程的隊列被調度時，cfq會優先檢查是否有非同步請求超時，就是超過fifo_expire_async參數的限制。如果有，則優先發送一個超時的請求，其餘請求仍然按照優先順序以及扇區編號大小來處理。
fifo_expire_sync:這個參數跟上面的類似，區別是用來設置同步請求的超時時間。
slice_idle:參數設置了一個等待時間。這讓cfq在切換cfq_queue或service tree的時候等待一段時間，目的是提高機械硬碟的吞吐量。
一般情況下，來自同一個cfq_queue或者service tree的IO請求的定址局部性更好，所以這樣可以減少磁碟的定址次數。這個值在機械硬碟上默認為非零。
當然在固態硬碟或者硬RAID設備上設置這個值為非零會降低存儲的效率，因為固態硬碟沒有磁頭定址這個概念，所以在這樣的設備上應該設置為0，關閉此功能。
group_idle:這個參數也跟上一個參數類似，區別是當cfq要切換cfq_group的時候會等待一段時間。
在cgroup的場景下，如果我們沿用slice_idle的方式，那麼空轉等待可能會在cgroup組內每個進程的cfq_queue切換時發生。
這樣會如果這個進程一直有請求要處理的話，那麼直到這個cgroup的配額被耗盡，同組中的其它進程也可能無法被調度到。這樣會導致同組中的其它進程餓死而產生IO性能瓶頸。
在這種情況下，我們可以將slice_idle ＝ 0而group_idle ＝ 8。這樣空轉等待就是以cgroup為單位進行的，而不是以cfq_queue的進程為單位進行，以防止上述問題產生。
low_latency:這個是用來開啟或關閉cfq的低延時（low latency）模式的開關。
當這個開關打開時，cfq將會根據target_latency的參數設置來對每一個進程的分片時間（slice time）進行重新計算。
這將有利於對吞吐量的公平（默認是對時間片分配的公平）。
關閉這個參數（設置為0）將忽略target_latency的值。這將使系統中的進程完全按照時間片方式進行IO資源分配。這個開關默認是打開的。
我們已經知道cfq設計上有「空轉」（idling）這個概念，目的是為了可以讓連續的讀寫操作盡可能多的合並處理，減少磁頭的定址操作以便增大吞吐量。
如果有進程總是很快的進行順序讀寫，那麼它將因為cfq的空轉等待命中率很高而導致其它需要處理IO的進程響應速度下降，如果另一個需要調度的進程不會發出大量順序IO行為的話，系統中不同進程IO吞吐量的表現就會很不均衡。
就比如，系統內存的cache中有很多臟頁要寫回時，桌面又要打開一個瀏覽器進行操作，這時臟頁寫回的後台行為就很可能會大量命中空轉時間，而導致瀏覽器的小量IO一直等待，讓用戶感覺瀏覽器運行響應速度變慢。
這個low_latency主要是對這種情況進行優化的選項，當其打開時，系統會根據target_latency的配置對因為命中空轉而大量佔用IO吞吐量的進程進行限制，以達到不同進程IO佔用的吞吐量的相對均衡。這個開關比較合適在類似桌面應用的場景下打開。
target_latency:當low_latency的值為開啟狀態時，cfq將根據這個值重新計算每個進程分配的IO時間片長度。
quantum:這個參數用來設置每次從cfq_queue中處理多少個IO請求。在一個隊列處理事件周期中，超過這個數字的IO請求將不會被處理。這個參數只對同步的請求有效。
slice_sync:當一個cfq_queue隊列被調度處理時，它可以被分配的處理總時間是通過這個值來作為一個計算參數指定的。公式為：time_slice = slice_sync + (slice_sync/5 * (4 - prio))。這個參數對同步請求有效。
slice_async:這個值跟上一個類似，區別是對非同步請求有效。
slice_async_rq:這個參數用來限制在一個slice的時間范圍內，一個隊列最多可以處理的非同步請求個數。請求被處理的最大個數還跟相關進程被設置的io優先順序有關。
1.3 cfq的IOPS模式
我們已經知道，默認情況下cfq是以時間片方式支持的帶優先順序的調度來保證IO資源佔用的公平。
高優先順序的進程將得到更多的時間片長度，而低優先順序的進程時間片相對較小。
當我們的存儲是一個高速並且支持NCQ（原生指令隊列）的設備的時候，我們最好可以讓其可以從多個cfq隊列中處理多路的請求，以便提升NCQ的利用率。
此時使用時間片的分配方式分配資源就顯得不合時宜了，因為基於時間片的分配，同一時刻最多能處理的請求隊列只有一個。
這時，我們需要切換cfq的模式為IOPS模式。切換方式很簡單，就是將slice_idle=0即可。內核會自動檢測你的存儲設備是否支持NCQ，如果支持的話cfq會自動切換為IOPS模式。
另外，在默認的基於優先順序的時間片方式下，我們可以使用ionice命令來調整進程的IO優先順序。進程默認分配的IO優先順序是根據進程的nice值計算而來的，計算方法可以在man ionice中看到，這里不再廢話。
2、deadline：最終期限調度
deadline調度演算法相對cfq要簡單很多。其設計目標是：
在保證請求按照設備扇區的順序進行訪問的同時，兼顧其它請求不被餓死，要在一個最終期限前被調度到。
我們知道磁頭對磁碟的尋道是可以進行順序訪問和隨機訪問的，因為尋道延時時間的關系，順序訪問時IO的吞吐量更大，隨機訪問的吞吐量小。
如果我們想為一個機械硬碟進行吞吐量優化的話，那麼就可以讓調度器按照盡量復合順序訪問的IO請求進行排序，之後請求以這樣的順序發送給硬碟，就可以使IO的吞吐量更大。
但是這樣做也有另一個問題，就是如果此時出現了一個請求，它要訪問的磁軌離目前磁頭所在磁軌很遠，應用的請求又大量集中在目前磁軌附近。
導致大量請求一直會被合並和插隊處理，而那個要訪問比較遠磁軌的請求將因為一直不能被調度而餓死。
deadline就是這樣一種調度器，能在保證IO最大吞吐量的情況下，盡量使遠端請求在一個期限內被調度而不被餓死的調度器。
㈣ epoll為什麼這么快epoll的實現原理是什麼
以一個生活中的例子來解釋.
假設你在大學中讀書,要等待一個朋友來訪,而這個朋友只知道你在A號樓,但是不知道你具體住在哪裡,於是你們約好了在A號樓門口見面.
如果你使用的阻塞IO模型來處理這個問題,那麼你就只能一直守候在A號樓門口等待朋友的到來,在這段時間里你不能做別的事情,不難知道,這種方式的效率是低下的.
進一步解釋select和epoll模型的差異.
select版大媽做的是如下的事情:比如同學甲的朋友來了,select版大媽比較笨,她帶著朋友挨個房間進行查詢誰是同學甲,你等的朋友來了,於是在實際的代碼中,select版大媽做的是以下的事情:
int n = select(&readset,NULL,NULL,100); for (int i = 0; n > 0; ++i) { if (FD_ISSET(fdarray[i], &readset)) { do_something(fdarray[i]); --n; } }epoll版大媽就比較先進了,她記下了同學甲的信息,比如說他的房間號,那麼等同學甲的朋友到來時,只需要告訴該朋友同學甲在哪個房間即可,不用自己親自帶著人滿大樓的找人了.於是epoll版大媽做的事情可以用如下的代碼表示:
n = epoll_wait(epfd,events,20,500); for(i=0;i<n;++i) { do_something(events[n]); } 在epoll中,關鍵的數據結構epoll_event定義如下:
typedef union epoll_data { void *ptr; int fd; __uint32_t u32; __uint64_t u64; } epoll_data_t; struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */ }; 可以看到,epoll_data是一個union結構體,它就是epoll版大媽用於保存同學信息的結構體,它可以保存很多類型的信息:fd,指針,等等.有了這個結構體,epoll大媽可以不用吹灰之力就可以定位到同學甲.
別小看了這些效率的提高,在一個大規模並發的伺服器中,輪詢IO是最耗時間的操作之一.再回到那個例子中,如果每到來一個朋友樓管大媽都要全樓的查詢同學,那麼處理的效率必然就低下了,過不久樓底就有不少的人了.
對比最早給出的阻塞IO的處理模型, 可以看到採用了多路復用IO之後, 程序可以自由的進行自己除了IO操作之外的工作, 只有到IO狀態發生變化的時候由多路復用IO進行通知, 然後再採取相應的操作, 而不用一直阻塞等待IO狀態發生變化了.
從上面的分析也可以看出,epoll比select的提高實際上是一個用空間換時間思想的具體應用.
二、深入理解epoll的實現原理：開發高性能網路程序時，windows開發者們言必稱iocp，linux開發者們則言必稱epoll。大家都明白epoll是一種IO多路復用技術，可以非常高效的處理數以百萬計的socket句柄，比起以前的select和poll效率高大發了。我們用起epoll來都感覺挺爽，確實快，那麼，它到底為什麼可以高速處理這么多並發連接呢？ 先簡單回顧下如何使用C庫封裝的3個epoll系統調用吧。int epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout); 使用起來很清晰，首先要調用epoll_create建立一個epoll對象。參數size是內核保證能夠正確處理的最大句柄數，多於這個最大數時內核可不保證效果。
epoll_ctl可以操作上面建立的epoll，例如，將剛建立的socket加入到epoll中讓其監控，或者把 epoll正在監控的某個socket句柄移出epoll，不再監控它等等。
epoll_wait在調用時，在給定的timeout時間內，當在監控的所有句柄中有事件發生時，就返回用戶態的進程。
從上面的調用方式就可以看到epoll比select/poll的優越之處：因為後者每次調用時都要傳遞你所要監控的所有socket給select/poll系統調用，這意味著需要將用戶態的socket列表到內核態，如果以萬計的句柄會導致每次都要幾十幾百KB的內存到內核態，非常低效。而我們調用epoll_wait時就相當於以往調用select/poll，但是這時卻不用傳遞socket句柄給內核，因為內核已經在epoll_ctl中拿到了要監控的句柄列表。
所以，實際上在你調用epoll_create後，內核就已經在內核態開始准備幫你存儲要監控的句柄了，每次調用epoll_ctl只是在往內核的數據結構里塞入新的socket句柄。
在內核里，一切皆文件。所以，epoll向內核注冊了一個文件系統，用於存儲上述的被監控socket。當你調用epoll_create時，就會在這個虛擬的epoll文件系統里創建一個file結點。當然這個file不是普通文件，它只服務於epoll。epoll在被內核初始化時（操作系統啟動），同時會開辟出epoll自己的內核高速cache區，用於安置每一個我們想監控的socket，這些socket會以紅黑樹的形式保存在內核cache里，以支持快速的查找、插入、刪除。這個內核高速cache區，就是建立連續的物理內存頁，然後在之上建立slab層，簡單的說，就是物理上分配好你想要的size的內存對象，每次使用時都是使用空閑的已分配好的對象。static int __init eventpoll_init(void) { ... ... /* Allocates slab cache used to allocate "struct epitem" items */ epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem), 0, SLAB_HWCACHE_ALIGN|EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); /* Allocates slab cache used to allocate "struct eppoll_entry" */ pwq_cache = kmem_cache_create("eventpoll_pwq", sizeof(struct eppoll_entry), 0, EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); ... ... epoll的高效就在於，當我們調用epoll_ctl往裡塞入百萬個句柄時，epoll_wait仍然可以飛快的返回，並有效的將發生事件的句柄給我們用戶。這是由於我們在調用epoll_create時，內核除了幫我們在epoll文件系統里建了個file結點，在內核cache里建了個紅黑樹用於存儲以後epoll_ctl傳來的socket外，還會再建立一個list鏈表，用於存儲准備就緒的事件，當epoll_wait調用時，僅僅觀察這個list鏈表裡有沒有數據即可。有數據就返回，沒有數據就sleep，等到timeout時間到後即使鏈表沒數據也返回。所以，epoll_wait非常高效。
那麼，這個准備就緒list鏈表是怎麼維護的呢？當我們執行epoll_ctl時，除了把socket放到epoll文件系統里file對象對應的紅黑樹上之外，還會給內核中斷處理程序注冊一個回調函數，告訴內核，如果這個句柄的中斷到了，就把它放到准備就緒list鏈表裡。所以，當一個socket上有數據到了，內核在把網卡上的數據到內核中後就來把socket插入到准備就緒鏈表裡了。
如此，一顆紅黑樹，一張准備就緒句柄鏈表，少量的內核cache，就幫我們解決了大並發下的socket處理問題。執行epoll_create時，創建了紅黑樹和就緒鏈表，執行epoll_ctl時，如果增加socket句柄，則檢查在紅黑樹中是否存在，存在立即返回，不存在則添加到樹幹上，然後向內核注冊回調函數，用於當中斷事件來臨時向准備就緒鏈表中插入數據。執行epoll_wait時立刻返回准備就緒鏈表裡的數據即可。
最後看看epoll獨有的兩種模式LT和ET。無論是LT和ET模式，都適用於以上所說的流程。區別是，LT模式下，只要一個句柄上的事件一次沒有處理完，會在以後調用epoll_wait時次次返回這個句柄，而ET模式僅在第一次返回。
這件事怎麼做到的呢？當一個socket句柄上有事件時，內核會把該句柄插入上面所說的准備就緒list鏈表，這時我們調用epoll_wait，會把准備就緒的socket拷貝到用戶態內存，然後清空准備就緒list鏈表，最後，epoll_wait幹了件事，就是檢查這些socket，如果不是ET模式（就是LT模式的句柄了），並且這些socket上確實有未處理的事件時，又把該句柄放回到剛剛清空的准備就緒鏈表了。所以，非ET的句柄，只要它上面還有事件，epoll_wait每次都會返回。而ET模式的句柄，除非有新中斷到，即使socket上的事件沒有處理完，也是不會次次從epoll_wait返回的。三、擴展閱讀（epoll與之前其他相關技術的比較）： Linux提供了select、poll、epoll介面來實現IO復用，三者的原型如下所示，本文從參數、實現、性能等方面對三者進行對比。 int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); int poll(struct pollfd *fds, nfds_t nfds, int timeout); int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout); select、poll、epoll_wait參數及實現對比 1． select的第一個參數nfds為fdset集合中最大描述符值加1，fdset是一個位數組，其大小限制為__FD_SETSIZE（1024），位數組的每一位代表其對應的描述符是否需要被檢查。 select的第二三四個參數表示需要關注讀、寫、錯誤事件的文件描述符位數組，這些參數既是輸入參數也是輸出參數，可能會被內核修改用於標示哪些描述符上發生了關注的事件。所以每次調用select前都需要重新初始化fdset。 timeout參數為超時時間，該結構會被內核修改，其值為超時剩餘的時間。 select對應於內核中的sys_select調用，sys_select首先將第二三四個參數指向的fd_set拷貝到內核，然後對每個被SET的描述符調用進行poll，並記錄在臨時結果中（fdset），如果有事件發生，select會將臨時結果寫到用戶空間並返回；當輪詢一遍後沒有任何事件發生時，如果指定了超時時間，則select會睡眠到超時，睡眠結束後再進行一次輪詢，並將臨時結果寫到用戶空間，然後返回。 select返回後，需要逐一檢查關注的描述符是否被SET（事件是否發生）。 2． poll與select不同，通過一個pollfd數組向內核傳遞需要關注的事件，故沒有描述符個數的限制，pollfd中的events欄位和revents分別用於標示關注的事件和發生的事件，故pollfd數組只需要被初始化一次。 poll的實現機制與select類似，其對應內核中的sys_poll，只不過poll向內核傳遞pollfd數組，然後對pollfd中的每個描述符進行poll，相比處理fdset來說，poll效率更高。 poll返回後，需要對pollfd中的每個元素檢查其revents值，來得指事件是否發生。 3． epoll通過epoll_create創建一個用於epoll輪詢的描述符，通過epoll_ctl添加/修改/刪除事件，通過epoll_wait檢查事件，epoll_wait的第二個參數用於存放結果。 epoll與select、poll不同，首先，其不用每次調用都向內核拷貝事件描述信息，在第一次調用後，事件信息就會與對應的epoll描述符關聯起來。另外epoll不是通過輪詢，而是通過在等待的描述符上注冊回調函數，當事件發生時，回調函數負責把發生的事件存儲在就緒事件鏈表中，最後寫到用戶空間。
㈤ 跳錶 && 紅黑樹
散列表：插入刪除查找都是O(1), 是最常用的，但其缺點是不能順序遍歷以及擴容縮容的性能損耗。適用於那些不需要順序遍歷，數據更新不那麼頻繁的。
跳錶(Skip list)：插入刪除查找都是O(logn), 並且能順序遍歷。缺點是空間復雜度O(n)。適用於不那麼在意內存空間的，其順序遍歷和區間查找非常方便。
紅黑樹：插入刪除查找都是O(logn), 中序遍歷即是順序遍歷，穩定。缺點是難以實現，去查找不方便。其實跳錶更佳，但紅黑樹已經用於很多地方了。
一、什麼是跳錶？
為一個值有序的鏈表建立多級索引，比如每2個節點提取一個節點到上一級，我們把抽出來的那一級叫做索引或索引層。如下圖所示，其中down表示down指針，指向下一級節點。以此類推，對於節點數為n的鏈表，大約可以建立log2n-1級索引。像這種為鏈表建立多級索引的數據結構就稱為跳錶。
二、跳錶的時間復雜度？
1.計算跳錶的高度
如果鏈表有n個節點，每2個節點抽取抽出一個節點作為上一級索引的節點，那第1級索引的節點個數大約是n/2，第2級索引的節點個數大約是n/4，依次類推，第k級索引的節點個數就是n/(2 k)。假設索引有h級別，最高級的索引有2個節點，則有n/(2 h)=2，得出h=log2n-1，包含原始鏈表這一層，整個跳錶的高度就是log2n。
2.計算跳錶的時間復雜度
假設我們在跳錶中查詢某個數據的時候，如果每一層都遍歷m個節點，那在跳錶中查詢一個數據的時間復雜度就是O(m*logn)。那這個m是多少呢？如下圖所示，假設我們要查找的數據是x，在第k級索引中，我們遍歷到y節點之後，發現x大於y，小於後面的節點z，所以我們通過y的down指針，從第k級下降到第k-1級索引。在第k-1級索引中，y和z之間只有3個節點（包含y和z），所以，我們在k-1級索引中最多隻需要遍歷3個節點，以此類推，每一級索引都最多隻需要遍歷3個節點。所以m=3。因此在跳錶中查詢某個數據的時間復雜度就是O(logn)。
三、跳錶的空間復雜度及如何優化？
1.計算索引的節點總數
如果鏈表有n個節點，每2個節點抽取抽出一個節點作為上一級索引的節點，那每一級索引的節點數分別為：n/2，n/4，n/8，…，8，4，2，等比數列求和n-1，所以跳錶的空間復雜度為O(n)。
2.如何優化時間復雜度
如果鏈表有n個節點，每3或5個節點抽取抽出一個節點作為上一級索引的節點，那每一級索引的節點數分別為（以3為例）：n/3，n/9，n/27，…，27，9，3，1，等比數列求和n/2，所以跳錶的空間復雜度為O(n)，和每2個節點抽取一次相比，時間復雜度要低不少呢。
四、高效的動態插入和刪除？
跳錶本質上就是鏈表，所以僅插作，插入和刪除操時間復雜度就為O(1)，但在實際情況中，要插入或刪除某個節點，需要先查找到指定位置，而這個查找操作比較費時，但在跳錶中這個查找操作的時間復雜度是O(logn)，所以，跳錶的插入和刪除操作的是時間復雜度也是O(logn)。
五、跳錶索引動態更新？
當往跳錶中插入數據的時候，可以選擇同時將這個數據插入到部分索引層中，那麼如何選擇這個索引層呢？可以通過隨機函數來決定將這個節點插入到哪幾級索引中，比如隨機函數生成了值K，那就可以把這個節點添加到第1級到第K級索引中。
㈥ 紅黑樹的用途
紅黑樹用在關聯數組、字典的實現上。需要的空間比散列表小。 任何鍵值對應,需要隨機存儲和鍵有序的情況都可以用。
㈦ php-紅黑樹、散列表、跳錶理解入門
就是把鏈表的結構稍加改造，這種數據結構叫
為了提升鏈表的查詢效率，怎麼讓鏈表支持類似『數組』那樣的『二分』演算法呢
跳錶是一個各方面性能都比較優秀的 動態數據結構 ，可以支持快速地插入、刪除、查找操作，寫起來也不復雜，甚至可以替代紅黑樹。
Redis 中的有序集合（Sorted Set）就是用跳錶來實現的。
那 Redis 為什麼會選擇用跳錶(和散列表)來實現有序集合呢？ 為什麼不用紅黑樹呢？這個問題一會在回答，先看看跳錶的數據結構
其實概念很簡單，就是在鏈表上加上了
當我們在不停插入數據，如果我們不更新索引，可能出現某 2 個索引結點之間數據非常多的情況。極端情況下，跳錶還會退化成單鏈表。
紅黑樹、AVL 樹這樣平衡二叉樹，是通過左右旋的方式保持左右子樹的大小平衡，而跳錶是通過 隨機函數 來維護平衡性。
插入、刪除、查找以及迭代輸出有序序列這幾個操作，紅黑樹也可以完成，時間復雜度跟跳錶是一樣的。但是， 按照區間來查找數據這個操作，紅黑樹的效率沒有跳錶高。
對於按照區間查找數據這個操作，跳錶可以做到 O(logn) 的時間復雜度定位區間的起點，然後在原始鏈表中順序往後遍歷就可以了。
Redis 鍵值構建一個散列表，這樣按照 key 來刪除、查找一個成員對象的時間復雜度就變成了 O(1)。同時，藉助跳錶結構，其他操作也非常高效。
散列表的英文叫「Hash Table」，我們平時也叫它「哈希表」或者「Hash 表」
散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系 f，使得每個關鍵字 key 對應一個存儲位置 f(key)。查找時根據這個對應關系匠互給定的 key 的映射 f(key)
這種關系 f 稱為散列函數（又稱哈希函數）。散列技術將記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散列表或哈希表。那麼關鍵字對應的記錄存儲位置稱為散列地址。
散列函數的構造方法特點就是：計算簡單、散列地址分布均勻
大家一定聽說過 hash 碰撞。就是2個不同的 key 對應著不同的 f 關系。但這是幾乎不可能的，即便像業界著名的MD5、SHA、CRC等哈希演算法，也無法完全避免這種散列沖突。而且，因為數組的存儲空間有限，也會加大散列沖突的概率。
我們只能通過其它途徑來尋找方法。我們常用的散列沖突解決方法有兩類，開放定址法（open addressing）和鏈表法（chaining）。
所謂的開放定址法就是一但發生了沖突，就去尋找下一個空的散地址，只要散列表足夠大，空的散列表地址總能找到，並將記錄存入。
鏈地址法又稱鏈表法，其實當發生沖突時存入鏈表，如下圖很容易就可以看明白。此時，已經不存在什麼沖突地址的問題，無論有多少沖突，都只是在當前位置給單鏈表增加結點的問題。
這種不常見，就是把沖突的單獨找個地方。
顧名思義，紅黑樹中的節點，一類被標記為黑色，一類被標記為紅色。除此之外，一棵紅黑
平衡二叉樹 是一種二叉排序樹，其中每一個節點的左子樹和右子樹的高度不能大於 1
紅黑樹是一種平衡二叉查找樹。它是為了解決普通二叉查找樹在數據更新的過程中，復雜度退化的問題而產生的。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查找操作的時間復雜度都是 O(logn)。
平衡二叉查找樹其實有很多，比如，Splay Tree（伸展樹）、Treap（樹堆）等，但是我們提到平衡二叉查找樹，聽到的基本都是紅黑樹。
紅黑樹在眾多裡面，表現的最為平衡。
「近似平衡」就等價為性能不會退化得太嚴重。
一棵紅黑樹還需要滿足這樣幾個要求：
看到這里你會很頭大，什麼黑的紅的，完全不懂。賦上連接，有時間在看
散列表 ：插入刪除查找都是O(1), 是最常用的，但其缺點是不能順序遍歷(存入的數據是無順序的)以及擴容縮容的性能損耗。適用於那些不需要順序遍歷，數據更新不那麼頻繁的。
散列表總和鏈表、跳錶一起出現組合使用。
跳錶 ：插入刪除查找都是O(logn), 並且能順序遍歷。缺點是空間復雜度O(n)。適用於不那麼在意內存空間的，其順序遍歷和區間查找非常方便。
跳錶還可以和散列表組合讓刪除、查找一個成員對象操作變為O(1)，也就是說利用了散列表查找速度，跳錶的順序結構
紅黑樹 ：插入刪除查找都是O(logn), 中序遍歷即是順序遍歷，穩定。缺點是難以實現，去查找不方便。其實跳錶更佳，但紅黑樹已經用於很多地方了。
㈧ 紅黑樹比起AVL樹具體更高效在什麼地方呢
優化了我的avl實現，AVL插入和刪除並不像教科書上說的，需要回溯到根節點，兩種情況下可以直接退出向上回溯：
插入更新時：如果當前節點的高度沒有改變，則停止向上回溯父節點。
刪除更新時：如果當前節點的高度沒有改變，且平衡值在[-1,1]區間則停止回溯。
最終結論，優化過的avl和linux的rbtree放在一起，avl真的和rbtree差不多，avl也並不總需要回溯到根節點，雖然旋轉次數多於rbtree，但是rbtree保持平衡除了旋轉外還有重新著色的操作，即便不旋轉也在拚命的重新著色，且層數較高，1百萬個節點的rbtree層數和1千萬個節點的avl相同。
所以查詢，刪除，插入全部放在一起來看，avl樹和rbtree差不多。
紅黑樹屬於平衡二叉樹。
說它不嚴格是因為它不是嚴格控制左、右子樹高度或節點數之差小於等於1。
但紅黑樹高度依然是平均log(n)，且最壞情況高度不會超過2log(n)，這有數學證明。所以它算平衡樹，只是不嚴格。不過嚴格與否並不影響數據結構的復雜度。
不用嚴格控制高度，使得插入效率更高。
1.查找
顯然，avl樹要比紅黑樹更平衡，因此avl樹的查找效率更高。
2.插入
不論是avl樹還是紅黑樹，旋轉的時間復雜度都是O(1)
對於avl樹，旋轉的時候，需要找到第一個不平衡節點，這就需要我們維護一個平衡因子，每一次插入，旋轉，刪除等操作，都要更新從跟節點到被修改節點這個路徑上的平衡因子。。。最差情況下，需要O(logn)的時間復雜度。。。
㈨ 紅黑樹，b+樹分別用於什麼場景，為什麼
紅黑樹屬於「黑平衡」的二叉樹，雖然犧牲了一定的平衡性，但是add、remove操作要由優於AVL樹也就是說RB-Tree的「統計性能」更佳！Java中TreeSet，TreeMap的底層都是基於RedBlackTree紅黑樹的；
B+樹主要用在文件系統以及資料庫做索引。比如磁碟存儲、文件系統、MySQL資料庫
㈩ STL的map為什麼用紅黑樹而不是哈希
用紅黑樹雖然速度可能會略遜於哈希，但是整體來說，應該更節省內存。
速度我們不說,肯定慢很多.
省內存,我們來分析一下.
一個紅黑樹的節點,有左右節點指針,和父節點指針,這就是三個指針的大小+value_type的大小;
unordered_map呢,開放地址法,就value_type,如果是開鏈法,那就是prev指針和next指針,倆指針+value_type
也就是說,當你的value_type越小,紅黑樹越浪費內存.
而hash table呢,主要是填充因子,比如0.5的填充因子,那麼那些桶是要浪費一些內存的.