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 的話，元素則不再集合内。
作者：邴越
掃碼關注公衆号：架構進化論，獲得第一手的技術資訊和原創文章
如果文章對您有幫助，可以點選文章右下角【推薦】一下，您的鼓勵是作者堅持原創和持續寫作的最大動力！