A. 資料庫索引的實現原理
資料庫索引的實現原理
一、概述資料庫索引，是資料庫管理系統中一個排序的數據結構，以協助快速查詢、更新資料庫表中數據。索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找演算法。這種數據結構，就是索引。其實說穿了，索引問題就是一個查找問題。二、索引的原理當我們的業務產生了大量的數據時，查找數據的效率問題也就隨之而來，所以我們可以通過為表設置索引，而為表設置索引要付出代價的：一是增加了資料庫的存儲空間，二是在插入和修改數據時要花費較多的時間(因為索引也要隨之變動)。
上圖展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址(注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的)。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的復雜度內獲取到相應數據。索引是建立在資料庫表中的某些列的上面。在創建索引的時候，應該考慮在哪些列上可以創建索引，在哪些列上不能創建索引。一般來說，應該在這些列上創建索引：在經常需要搜索的列上，可以加快搜索的速度;在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構;在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度;在經常需要根據范圍進行搜索的列上創建索引，因為索引已經排序，其指定的范圍是連續的;在經常需要排序的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間;在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度。創建索引可以大大提高系統的性能第一，通過創建唯一性索引，可以保證資料庫表中每一行數據的唯一性。第二，可以大大加快數據的檢索速度，這也是創建索引的最主要的原因。第三，可以加速表和表之間的連接，特別是在實現數據的參考完整性方面特別有意義。第四，在使用分組和排序子句進行數據檢索時，同樣可以顯著減少查詢中分組和排序的時間。第五，通過使用索引，可以在查詢的過程中，使用優化隱藏器，提高系統的性能。也許會有人要問：增加索引有如此多的優點，為什麼不對表中的每一個列創建一個索引呢?因為，增加索引也有許多不利的方面。創建索引的弊端第一，創建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增加。第二，索引需要佔物理空間，除了數據表占數據空間之外，每一個索引還要佔一定的物理空間，如果要建立聚簇索引，那麼需要的空間就會更大。第三，當對表中的數據進行增加、刪除和修改的時候，索引也要動態的維護，這樣就降低了數據的維護速度。同樣，對於有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：第一，對於那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，並不能提高查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。第二，對於那些只有很少數據值的列也不應該增加索引。這是因為，由於這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行佔了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，並不能明顯加快檢索速度。第三，對於那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要麼相當大，要麼取值很少。第四，當修改性能遠遠大於檢索性能時，不應該創建索引。這是因為，修改性能和檢索性能是互相矛盾的。當增加索引時，會提高檢索性能，但是會降低修改性能。當減少索引時，會提高修改性能，降低檢索性能。因此，當修改性能遠遠大於檢索性能時，不應該創建索引。三、索引的類型根據資料庫的功能，可以在資料庫設計器中創建三種索引：唯一索引、主鍵索引和聚集索引。唯一索引唯一索引是不允許其中任何兩行具有相同索引值的索引。當現有數據中存在重復的鍵值時，大多數資料庫不允許將新創建的唯一索引與表一起保存。資料庫還可能防止添加將在表中創建重復鍵值的新數據。例如，如果在employee表中職員的姓(lname)上創建了唯一索引，則任何兩個員工都不能同姓。主鍵索引資料庫表經常有一列或列組合，其值唯一標識表中的每一行。該列稱為表的主鍵。在資料庫關系圖中為表定義主鍵將自動創建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個值都唯一。當在查詢中使用主鍵索引時，它還允許對數據的快速訪問。聚集索引在聚集索引中，表中行的物理順序與鍵值的邏輯(索引)順序相同。一個表只能包含一個聚集索引。如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數據訪問速度。四、局部性原理與磁碟預讀由於存儲介質的特性，磁碟本身存取就比主存慢很多，再加上機械運動耗費，磁碟的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁碟I/O。為了達到這個目的，磁碟往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁碟也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用。程序運行期間所需要的數據通常比較集中。由於磁碟順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，因此對於具有局部性的程序來說，預讀可以提高I/O效率。預讀的長度一般為頁(page)的整倍數。頁是計算機管理存儲器的邏輯塊，硬體及操作系統往往將主存和磁碟存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統中，頁得大小通常為4k)，主存和磁碟以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁碟發出讀盤信號，磁碟會找到數據的起始位置並向後連續讀取一頁或幾頁載入內存中，然後異常返回，程序繼續運行。五、B樹和B+樹數據結構1、B樹B樹中每個節點包含了鍵值和鍵值對於的數據對象存放地址指針，所以成功搜索一個對象可以不用到達樹的葉節點。成功搜索包括節點內搜索和沿某一路徑的搜索，成功搜索時間取決於關鍵碼所在的層次以及節點內關鍵碼的數量。在B樹中查找給定關鍵字的方法是：首先把根結點取來，在根結點所包含的關鍵字K1,…,kj查找給定的關鍵字(可用順序查找或二分查找法)，若找到等於給定值的關鍵字，則查找成功;否則，一定可以確定要查的關鍵字在某個Ki或Ki+1之間，於是取Pi所指的下一層索引節點塊繼續查找，直到找到，或指針Pi為空時查找失敗。2、B+樹B+樹非葉節點中存放的關鍵碼並不指示數據對象的地址指針，非也節點只是索引部分。所有的葉節點在同一層上，包含了全部關鍵碼和相應數據對象的存放地址指針，且葉節點按關鍵碼從小到大順序鏈接。如果實際數據對象按加入的順序存儲而不是按關鍵碼次數存儲的話，葉節點的索引必須是稠密索引，若實際數據存儲按關鍵碼次序存放的話，葉節點索引時稀疏索引。B+樹有2個頭指針，一個是樹的根節點，一個是最小關鍵碼的葉節點。所以 B+樹有兩種搜索方法：一種是按葉節點自己拉起的鏈表順序搜索。一種是從根節點開始搜索，和B樹類似，不過如果非葉節點的關鍵碼等於給定值，搜索並不停止，而是繼續沿右指針，一直查到葉節點上的關鍵碼。所以無論搜索是否成功，都將走完樹的所有層。B+ 樹中，數據對象的插入和刪除僅在葉節點上進行。這兩種處理索引的數據結構的不同之處：1、B樹中同一鍵值不會出現多次，並且它有可能出現在葉結點，也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中，並且有可能在非葉結點中也有可能重復出現，以維持B+樹的平衡。2、因為B樹鍵位置不定，且在整個樹結構中只出現一次，雖然可以節省存儲空間，但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。3、B樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同(在葉結點的時候)，最小時間復雜度為1(在根結點的時候)。而B+樹的時候復雜度對某建成的樹是固定的。六、B/+Tree索引的性能分析到這里終於可以分析B-/+Tree索引的性能了。上文說過一般使用磁碟I/O次數評價索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要訪問h個節點。資料庫系統的設計者巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B-Tree還需要使用如下技巧：每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。B-Tree中一次檢索最多需要h-1次I/O(根節點常駐內存)，漸進復雜度為O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小(通常不超過3)。而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。綜上所述，用B-Tree作為索引結構效率是非常高的。
B. 為什麼HashMap使用紅黑樹而不使用AVL樹
紅黑樹適用於大量插入和刪除；因為它是非嚴格的平衡樹；只要從根節點到葉子節點的最長路徑不超過最短路徑的2倍，就不進行平衡調節
AVL樹是嚴格的平衡樹，上述的最短路徑與最長路徑的差不能超過|1|，AVL允許的差值小；在進行大量插入和刪除操作時，頻繁地進行平衡調整會嚴重降低效率；
紅黑樹雖然不是嚴格的平衡樹，但是其依舊是平衡樹；查找效率是logn；
AVL也是logn；
紅黑樹捨去了嚴格的平衡，使其插入，刪除，查找的效率穩定在O(logn)
反觀AVL樹，查找沒問題O(logn)，但是為了保證高度平衡，動態插入和刪除的代價也隨之增加，綜合效率肯定達不到O(logn)
所以在進行大量插入，刪除操作時，紅黑樹更優一些
Hashmap用到數據結構有
數組，鏈表，紅黑樹
在沒有地址沖突時，效率O(1)
有少量地址沖突，在沖突的地址拉鏈(建鏈表)，效率在O(1)~O(logn)之間
有大量地址沖突，在沖突的地址建紅黑樹，效率O(logn)
C. 基於資料庫搜索的演算法，關鍵有哪幾點
B+、B- Tree(mysql,oracle,mongodb)
主要用在關系資料庫的索引中，如oracle，mysql innodb；mongodb中的索引也是B-樹實現的；還有HBase中HFile中的DataBlock的索引等等。
動態查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（Balanced Binary Search Tree），紅黑樹(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找樹結構，其查找的時間復雜度O(log2N)與樹的深度相關，那麼降低樹的深度自然會提高查找效率。
但是咱們有面對這樣一個實際問題：就是大規模數據存儲中，實現索引查詢這樣一個實際背景下，樹節點存儲的元素數量是有限的（如果元素數量非常多的話，查找就退化成節點內部的線性查找了），這樣導致二叉查找樹結構由於樹的深度過大而造成磁碟I/O讀寫過於頻繁，進而導致查詢效率低下，那麼如何減少樹的深度（當然是不能減少查詢的數據量），一個基本的想法就是：採用多叉樹結構（由於樹節點元素數量是有限的，自然該節點的子樹數量也就是有限的）。
也就是說，因為磁碟的操作費時費資源，如果過於頻繁的多次查找勢必效率低下。那麼如何提高效率，即如何避免磁碟過於頻繁的多次查找呢？根據磁碟查找存取的次數往往由樹的高度所決定，所以，只要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度，那麼是不是便能有效減少磁碟查找存取的次數呢？那這種有效的樹結構是一種怎樣的樹呢？
這樣我們就提出了一個新的查找樹結構——多路查找樹。根據平衡二叉樹的啟發，自然就想到平衡多路查找樹結構，也就是B~tree，即B樹結構(後面，我們將看到，B樹的各種操作能使B樹保持較低的高度，從而達到有效避免磁碟過於頻繁的查找存取操作，從而有效提高查找效率)。
Hash表+桶(redis)
mysql中的adaptive hash index，redis中的數據存儲實現都是採用hash，可以高效的進行數據的查詢。
哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
哈希表的做法其實很簡單，就是把Key通過一個固定的演算法函數既所謂的哈希函數轉換成一個整型數字，然後就將該數字對數組長度進行取余，取余結果就當作數組的下標，將value存儲在以該數字為下標的數組空間里。
而當使用哈希表進行查詢的時候，就是再次使用哈希函數將key轉換為對應的數組下標，並定位到該空間獲取value，如此一來，就可以充分利用到數組的定位性能進行數據定位
數組的特點是：定址容易，插入和刪除困難；而鏈表的特點是：定址困難，插入和刪除容易。綜合兩者特性，設計一種定址容易，插入刪除也容易的數據結構，如拉鏈法實現的哈希表。
Booleam Filter（HBase）
HBase中的rowkey設置建立Booleam Filter映射，用於快速判斷rowkey是否在一個HFile中。在分布式資料庫中用的比較多。
基於BitMap的存儲結構，採用的是哈希函數的方法，將一個元素映射到一個 m 長度的陣列上的一個點，當這個點是 1 時，那麼這個元素在集合內，反之則不在集合內。這個方法的缺點就是當檢測的元素量很多時候可能有沖突，解決方法就是使用 k 個哈希 函數對應 k 個點，如果所有點都是 1 的話，那麼元素在集合內，如果有 0 的話，元素則不再集合內。
D. 為什麼HashMap使用紅黑樹而不使用AVL樹
AVL樹和紅黑樹有幾點比較和區別：
（1）AVL樹是更加嚴格的平衡，因此可以提供更快的查找速度，一般讀取查找密集型任務，適用AVL樹。
（2）紅黑樹更適合於插入修改密集型任務。
（3）通常，AVL樹的旋轉比紅黑樹的旋轉更加難以平衡和調試。
總結：
（1）AVL以及紅黑樹是高度平衡的樹數據結構。它們非常相似，真正的區別在於在任何添加/刪除操作時完成的旋轉操作次數。
（2）兩種實現都縮放為a O(lg N)，其中N是葉子的數量，但實際上AVL樹在查找密集型任務上更快：利用更好的平衡，樹遍歷平均更短。另一方面，插入和刪除方面，AVL樹速度較慢：需要更高的旋轉次數才能在修改時正確地重新平衡數據結構。
（3）在AVL樹中，從根到任何葉子的最短路徑和最長路徑之間的差異最多為1。在紅黑樹中，差異可以是2倍。
（4）兩個都給O（log n）查找，但平衡AVL樹可能需要O（log n）旋轉，而紅黑樹將需要最多兩次旋轉使其達到平衡（盡管可能需要檢查O（log n）節點以確定旋轉的位置）。旋轉本身是O（1）操作，因為你只是移動指針。
E. 為什麼像map，set都用紅黑樹來實現
STL中List,Vector,Map,Set的理解2009年07月11日 星期六 21:27List封裝了鏈表,Vector封裝了數組, list和vector得最主要的區別在於vector使用連續內存存儲的，他支持[]運算符，而list是以鏈表形式實現的，不支持[]。Vector對於隨機訪問的速度很快，但是對於插入尤其是在頭部插入元素速度很慢，在尾部插入速度很快。List對於隨機訪問速度慢得多，因為可能要遍歷整個鏈表才能做到，但是對於插入就快的多了，不需要拷貝和移動數據，只需要改變指針的指向就可以了。另外對於新添加的元素，Vector有一套演算法，而List可以任意加入。Map,Set屬於標准關聯容器，使用了非常高效的平衡檢索二叉樹：紅黑樹，他的插入刪除效率比其他序列容器高是因為不需要做內存拷貝和內存移動，而直接替換指向節點的指針即可。Set和Vector的區別在於Set不包含重復的數據。Set和Map的區別在於Set只含有Key，而Map有一個Key和Key所對應的Value兩個元素。Map和Hash_Map的區別是Hash_Map使用了Hash演算法來加快查找過程，但是需要更多的內存來存放這些Hash桶元素，因此可以算得上是採用空間來換取時間策略。
F. 資料庫索引的底層實現是什麼數據結構
關於資料庫索引的數據結構，大多數資料庫都是採用B樹。可參照文章：
http://blog.csdn.net/Ant_Yan/archive/2008/09/15/2932068.aspx
非主鍵索引需要在數據表本身的存儲空間外額外開銷存儲空間，所以在更新的時候可能不僅要更新數據表本身，還要更新非主鍵索引，更新內容更多了，所以導致速度降低。反過來，如果數據表中的數據按照主鍵索引的順序存儲，更新的時候就沒有額外的開銷。
非主鍵索引對提高查詢速度來講，主要的方面是：檢索的條件(where...)如果命中對應的非主鍵索引的話，就不需要對數據表做全表掃描，效率肯定是大大提高。（索引的創建和使用是資料庫設計和優化的重要部分，是一個資料庫程序員的必修課，不同資料庫系統的語法不同，但是原理基本相同）;
另一方面，也有如下的可能：如果檢索結果的欄位包含在非主鍵索引中，即使對非主鍵索引做全掃描，也比對整表欄位做全掃描快，因為只有非主鍵索引本身的數據需要從存儲設備調入內存，節約了IO時間。
不過一般說索引對查詢速度的影響，主要指第一種情況。
G. 為什麼mysql的數據結構用的是b+而不是b
mysql的數據結構用的是b+而不是b
紅黑樹等數據結構也可以用來實現索引，但是文件系統及資料庫系統普遍採用B-/+Tree作為索引結構，這一節將結合計算機組成原理相關知識討論B-/+Tree作為索引的理論基礎。
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁碟上。這樣的話，索引查找過程中就要產生磁碟I/O消耗，相對於內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁碟I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁碟I/O的存取次數。下面先介紹內存和磁碟存取原理，然後再結合這些原理分析B-/+Tree作為索引的效率。
主存存取原理
目前計算機使用的主存基本都是隨機讀寫存儲器（RAM），現代RAM的結構和存取原理比較復雜，這里本文拋卻具體差別，抽象出一個十分簡單的存取模型來說明RAM的工作原理。
圖5
從抽象角度看，主存是一系列的存儲單元組成的矩陣，每個存儲單元存儲固定大小的數據。每個存儲單元有唯一的地址，現代主存的編址規則比較復雜，這里將其簡化成一個二維地址：通過一個行地址和一個列地址可以唯一定位到一個存儲單元。圖5展示了一個4 x 4的主存模型。
主存的存取過程如下：
當系統需要讀取主存時，則將地址信號放到地址匯流排上傳給主存，主存讀到地址信號後，解析信號並定位到指定存儲單元，然後將此存儲單元數據放到數據匯流排上，供其它部件讀取。
寫主存的過程類似，系統將要寫入單元地址和數據分別放在地址匯流排和數據匯流排上，主存讀取兩個匯流排的內容，做相應的寫操作。
這里可以看出，主存存取的時間僅與存取次數呈線性關系，因為不存在機械操作，兩次存取的數據的「距離」不會對時間有任何影響，例如，先取A0再取A1和先取A0再取D3的時間消耗是一樣的。
磁碟存取原理
上文說過，索引一般以文件形式存儲在磁碟上，索引檢索需要磁碟I/O操作。與主存不同，磁碟I/O存在機械運動耗費，因此磁碟I/O的時間消耗是巨大的。
圖6是磁碟的整體結構示意圖。
圖6
一個磁碟由大小相同且同軸的圓形碟片組成，磁碟可以轉動（各個磁碟必須同步轉動）。在磁碟的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁碟的內容。磁頭不能轉動，但是可以沿磁碟半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。
H. java中哪些數據結構使用了紅黑樹
參考資料的網頁上有比較的代碼,你可以仔細看下~~~
java中HashMap,LinkedHashMap,TreeMap，HashTable的區別
java為數據結構中的映射定義了一個介面java.util.Map;它有四個實現類,分別是HashMap Hashtable LinkedHashMap 和TreeMap
Map主要用於存儲健值對，根據鍵得到值，因此不允許鍵重復(重復了覆蓋了),但允許值重復。
Hashmap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度，遍歷時，取得數據的順序是完全隨機的。HashMap最多隻允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導致數據的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
Hashtable與 HashMap類似,它繼承自Dictionary類，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步，即任一時刻只有一個線程能寫Hashtable,因此也導致了 Hashtable在寫入時會比較慢。
LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關。
TreeMap實現SortMap介面，能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。
一般情況下，我們用的最多的是HashMap,HashMap裡面存入的鍵值對在取出的時候是隨機的,它根據鍵的HashCode值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度。在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。
TreeMap取出來的是排序後的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那麼TreeMap會更好。
LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那麼用LinkedHashMap可以實現,它還可以按讀取順序來排列，像連接池中可以應用。
I. 為什麼treeset使用紅黑樹而一些資料庫索引使用b樹和b+樹
為什麼treeset使用紅黑樹而一些資料庫索引使用b樹和b+樹
在C++
STL中，很多部分(目前包括set,
multiset,
map,
multimap)應用了紅黑樹的變體(SGI
STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。
J. 為什麼treeset使用紅黑樹而一些資料庫索引使用b樹和b+樹
為什麼treeset使用紅黑樹而一些資料庫索引使用b樹和b+樹
在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。