目錄

[1. 順序查找]
[2. 二分查找]
[3. 插值查找]
[4. 斐波那契查找]
[5. 樹(shù)表查找]
[6. 分塊查找]
[7. 哈希查找]

本文簡(jiǎn)單概括性的介紹了常見(jiàn)的七種查找算法附迷，說(shuō)是七種，其實(shí)二分查找、插值查找以及斐波那契查找都可以歸為一類(lèi)——插值查找术荤。插值查找和斐波那契查找是在二分查找的基礎(chǔ)上的優(yōu)化查找算法砂蔽。樹(shù)表查找和哈希查找會(huì)在后續(xù)的博文中進(jìn)行詳細(xì)介紹峭状。

查找定義：根據(jù)給定的某個(gè)值蛛砰，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）芍殖。

• 查找算法分類(lèi)：
  　　1）靜態(tài)查找和動(dòng)態(tài)查找疾嗅；
  　　　　注：靜態(tài)或者動(dòng)態(tài)都是針對(duì)查找表而言的外厂。動(dòng)態(tài)表指查找表中有刪除和插入操作的表。
  　　2）無(wú)序查找和有序查找代承。
  　　　　無(wú)序查找：被查找數(shù)列有序無(wú)序均可汁蝶；
  　　　　有序查找：被查找數(shù)列必須為有序數(shù)列。

• 平均查找長(zhǎng)度（Average Search Length论悴，ASL）：需和指定key進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值掖棉，稱(chēng)為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。
  　　對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表膀估，查找成功的平均查找長(zhǎng)度為：ASL = Pi*Ci的和幔亥。
  　　Pi：查找表中第i個(gè)數(shù)據(jù)元素的概率。
  　　Ci：找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過(guò)的次數(shù)察纯。

1. 順序查找

• 說(shuō)明：順序查找適合于存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)或鏈接存儲(chǔ)的線性表帕棉。

• 基本思想：順序查找也稱(chēng)為線形查找，屬于無(wú)序查找算法饼记。從數(shù)據(jù)結(jié)構(gòu)線形表的一端開(kāi)始香伴，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值k相比較具则，若相等則表示查找成功即纲；若掃描結(jié)束仍沒(méi)有找到關(guān)鍵字等于k的結(jié)點(diǎn)，表示查找失敗博肋。
  　　復(fù)雜度分析：　
  　　查找成功時(shí)的平均查找長(zhǎng)度為：（假設(shè)每個(gè)數(shù)據(jù)元素的概率相等） ASL = 1/n * (1+2+3+…+n) = (n+1)/2 ;
  　　當(dāng)查找不成功時(shí)低斋，需要n+1次比較，時(shí)間復(fù)雜度為O(n);
  　　所以束昵，順序查找的時(shí)間復(fù)雜度為O(n)拔稳。

2. 二分查找

• 說(shuō)明：元素必須是有序的，如果是無(wú)序的則要先進(jìn)行排序操作锹雏。

• 基本思想：也稱(chēng)折半查找巴比，屬于有序查找算法。用給定值k先與中間結(jié)點(diǎn)的關(guān)鍵字比較，中間結(jié)點(diǎn)把線形表分成兩個(gè)子表轻绞，若相等則查找成功采记；若不相等，再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果確定下一步查找哪個(gè)子表政勃，這樣遞歸進(jìn)行唧龄，直到查找到或查找結(jié)束發(fā)現(xiàn)表中沒(méi)有這樣的結(jié)點(diǎn)。

• 復(fù)雜度分析：最壞情況下奸远，關(guān)鍵詞比較次數(shù)為log2(n+1)既棺，且期望時(shí)間復(fù)雜度為O(log2n)；

注：折半查找的前提條件是需要有序表順序存儲(chǔ)懒叛，對(duì)于靜態(tài)查找表丸冕，一次排序后不再變化，折半查找能得到不錯(cuò)的效率薛窥。但對(duì)于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來(lái)說(shuō)胖烛，維護(hù)有序的排序會(huì)帶來(lái)不小的工作量，那就不建議使用诅迷∨宸——《大話數(shù)據(jù)結(jié)構(gòu)》

//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找罢杉，遞歸版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

3. 插值查找

在介紹插值查找之前趟畏，首先考慮一個(gè)新問(wèn)題，為什么上述算法一定要是折半屑那，而不是折四分之一或者折更多呢拱镐？
　　打個(gè)比方，在英文字典里面查“apple”持际，你下意識(shí)翻開(kāi)字典是翻前面的書(shū)頁(yè)還是后面的書(shū)頁(yè)呢？如果再讓你查“zoo”哗咆，你又怎么查蜘欲？很顯然，這里你絕對(duì)不會(huì)是從中間開(kāi)始查起晌柬，而是有一定目的的往前或往后翻姥份。
　　同樣的，比如要在取值范圍1 ~ 10000 之間 100 個(gè)元素從小到大均勻分布的數(shù)組中查找5年碘， 我們自然會(huì)考慮從數(shù)組下標(biāo)較小的開(kāi)始查找澈歉。
　　經(jīng)過(guò)以上分析，折半查找這種查找方式屿衅，不是自適應(yīng)的（也就是說(shuō)是傻瓜式的）埃难。二分查找中查找點(diǎn)計(jì)算如下：
　　mid=(low+high)/2, 即mid=low+1/2*(high-low);
　　通過(guò)類(lèi)比，我們可以將查找的點(diǎn)改進(jìn)為如下：
　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
　　也就是將上述的比例參數(shù)1/2改進(jìn)為自適應(yīng)的涡尘，根據(jù)關(guān)鍵字在整個(gè)有序表中所處的位置忍弛，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了比較次數(shù)考抄。
　　基本思想：基于二分查找算法细疚，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，可以提高查找效率川梅。當(dāng)然疯兼，差值查找也屬于有序查找。
　　注：對(duì)于表長(zhǎng)較大贫途，而關(guān)鍵字分布又比較均勻的查找表來(lái)說(shuō)镇防，插值查找算法的平均性能比折半查找要好的多。反之潮饱，數(shù)組中如果分布非常不均勻来氧，那么插值查找未必是很合適的選擇。
　　復(fù)雜度分析：查找成功或者失敗的時(shí)間復(fù)雜度均為O(log2(log2n))香拉。

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}

4. 斐波那契查找

在介紹斐波那契查找算法之前啦扬，我們先介紹一下很它緊密相連并且大家都熟知的一個(gè)概念——黃金分割。

黃金比例又稱(chēng)黃金分割凫碌，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系扑毡，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比盛险，其比值約為1:0.618或1.618:1瞄摊。

0.618被公認(rèn)為最具有審美意義的比例數(shù)字，這個(gè)數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫(huà)苦掘、雕塑换帜、音樂(lè)、建筑等藝術(shù)領(lǐng)域鹤啡，而且在管理惯驼、工程設(shè)計(jì)等方面也有著不可忽視的作用。因此被稱(chēng)為黃金分割递瑰。

大家記不記得斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（從第三個(gè)數(shù)開(kāi)始祟牲，后邊每一個(gè)數(shù)都是前兩個(gè)數(shù)的和）。然后我們會(huì)發(fā)現(xiàn)抖部，隨著斐波那契數(shù)列的遞增说贝，前后兩個(gè)數(shù)的比值會(huì)越來(lái)越接近0.618，利用這個(gè)特性慎颗，我們就可以將黃金比例運(yùn)用到查找技術(shù)中乡恕。

基本思想：也是二分查找的一種提升算法言询，通過(guò)運(yùn)用黃金比例的概念在數(shù)列中選擇查找點(diǎn)進(jìn)行查找，提高查找效率几颜。同樣地倍试，斐波那契查找也屬于一種有序查找算法。
　　相對(duì)于折半查找蛋哭，一般將待比較的key值與第mid=（low+high）/2位置的元素比較县习，比較結(jié)果分三種情況：
　　1）相等，mid位置的元素即為所求
　　2）>谆趾，low=mid+1;
　　3）<躁愿，high=mid-1。

斐波那契查找與折半查找很相似沪蓬，他是根據(jù)斐波那契序列的特點(diǎn)對(duì)有序表進(jìn)行分割的彤钟。他要求開(kāi)始表中記錄的個(gè)數(shù)為某個(gè)斐波那契數(shù)小1，及n=F(k)-1;

開(kāi)始將k值與第F(k-1)位置的記錄進(jìn)行比較(及mid=low+F(k-1)-1),比較結(jié)果也分為三種

1）相等跷叉，mid位置的元素即為所求

2）>逸雹，low=mid+1,k-=2;

說(shuō)明：low=mid+1說(shuō)明待查找的元素在[mid+1,high]范圍內(nèi)，k-=2 說(shuō)明范圍[mid+1,high]內(nèi)的元素個(gè)數(shù)為n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個(gè)云挟，所以可以遞歸的應(yīng)用斐波那契查找梆砸。

3）<，high=mid-1,k-=1园欣。

說(shuō)明：low=mid+1說(shuō)明待查找的元素在[low,mid-1]范圍內(nèi)帖世，k-=1 說(shuō)明范圍[low,mid-1]內(nèi)的元素個(gè)數(shù)為F(k-1)-1個(gè)，所以可以遞歸 的應(yīng)用斐波那契查找沸枯。

復(fù)雜度分析：最壞情況下日矫，時(shí)間復(fù)雜度為O(log2n)，且其期望復(fù)雜度也為O(log2n)绑榴。

5. 樹(shù)表查找

5.1 最簡(jiǎn)單的樹(shù)表查找算法——二叉樹(shù)查找算法哪轿。

基本思想：二叉查找樹(shù)是先對(duì)待查找的數(shù)據(jù)進(jìn)行生成樹(shù)，確保樹(shù)的左分支的值小于右分支的值彭沼，然后在就行和每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)比較大小缔逛，查找最適合的范圍。 這個(gè)算法的查找效率很高姓惑，但是如果使用這種查找方法要首先創(chuàng)建樹(shù)。

二叉查找樹(shù)（BinarySearch Tree按脚，也叫二叉搜索樹(shù)于毙，或稱(chēng)二叉排序樹(shù)Binary Sort Tree）或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

1）若任意節(jié)點(diǎn)的左子樹(shù)不空辅搬，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值唯沮；

2）若任意節(jié)點(diǎn)的右子樹(shù)不空脖旱，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

3）任意節(jié)點(diǎn)的左介蛉、右子樹(shù)也分別為二叉查找樹(shù)萌庆。

二叉查找樹(shù)性質(zhì)：對(duì)二叉查找樹(shù)進(jìn)行中序遍歷，即可得到有序的數(shù)列币旧。

不同形態(tài)的二叉查找樹(shù)如下圖所示：

復(fù)雜度分析：它和二分查找一樣践险，插入和查找的時(shí)間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會(huì)有O(n)的時(shí)間復(fù)雜度吹菱。原因在于插入和刪除元素的時(shí)候巍虫，樹(shù)沒(méi)有保持平衡（比如，我們查找上圖（b）中的“93”鳍刷，我們需要進(jìn)行n次查找操作）占遥。我們追求的是在最壞的情況下仍然有較好的時(shí)間復(fù)雜度，這就是平衡查找樹(shù)設(shè)計(jì)的初衷输瓜。

基于二叉查找樹(shù)進(jìn)行優(yōu)化瓦胎，進(jìn)而可以得到其他的樹(shù)表查找算法，如平衡樹(shù)尤揣、紅黑樹(shù)等高效算法搔啊。

5.2 平衡查找樹(shù)之2-3查找樹(shù)（2-3 Tree）

• 2-3查找樹(shù)定義：和二叉樹(shù)不一樣，2-3樹(shù)運(yùn)行每個(gè)節(jié)點(diǎn)保存1個(gè)或者兩個(gè)的值芹缔。對(duì)于普通的2節(jié)點(diǎn)(2-node)坯癣，他保存1個(gè)key和左右兩個(gè)自己點(diǎn)。對(duì)應(yīng)3節(jié)點(diǎn)(3-node)最欠，保存兩個(gè)Key示罗，2-3查找樹(shù)的定義如下：

1）要么為空，要么：

2）對(duì)于2節(jié)點(diǎn)芝硬，該節(jié)點(diǎn)保存一個(gè)key及對(duì)應(yīng)value蚜点，以及兩個(gè)指向左右節(jié)點(diǎn)的節(jié)點(diǎn)，左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)拌阴，所有的值都比key要小绍绘，右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值比key要大迟赃。

3）對(duì)于3節(jié)點(diǎn)陪拘，該節(jié)點(diǎn)保存兩個(gè)key及對(duì)應(yīng)value，以及三個(gè)指向左中右的節(jié)點(diǎn)纤壁。左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)左刽，所有的值均比兩個(gè)key中的最小的key還要小酌媒；中間節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)欠痴，中間節(jié)點(diǎn)的key值在兩個(gè)跟節(jié)點(diǎn)key值之間迄靠；右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，節(jié)點(diǎn)的所有key值比兩個(gè)key中的最大的key還要大喇辽。

• 2-3查找樹(shù)的性質(zhì)：

1）如果中序遍歷2-3查找樹(shù)掌挚，就可以得到排好序的序列；

2）在一個(gè)完全平衡的2-3查找樹(shù)中菩咨，根節(jié)點(diǎn)到每一個(gè)為空節(jié)點(diǎn)的距離都相同吠式。（這也是平衡樹(shù)中“平衡”一詞的概念，根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)距離對(duì)應(yīng)于查找算法的最壞情況旦委，而平衡樹(shù)中根節(jié)點(diǎn)到葉節(jié)點(diǎn)的距離都一樣奇徒，最壞情況也具有對(duì)數(shù)復(fù)雜度。）

性質(zhì)2）如下圖所示：

• 復(fù)雜度分析：

2-3樹(shù)的查找效率與樹(shù)的高度是息息相關(guān)的缨硝。

在最壞的情況下摩钙，也就是所有的節(jié)點(diǎn)都是2-node節(jié)點(diǎn)，查找效率為lgN
在最好的情況下查辩，所有的節(jié)點(diǎn)都是3-node節(jié)點(diǎn)胖笛，查找效率為log3N約等于0.631lgN
　　距離來(lái)說(shuō)，對(duì)于1百萬(wàn)個(gè)節(jié)點(diǎn)的2-3樹(shù)宜岛，樹(shù)的高度為12-20之間驰弄，對(duì)于10億個(gè)節(jié)點(diǎn)的2-3樹(shù)柬甥，樹(shù)的高度為18-30之間。

對(duì)于插入來(lái)說(shuō)，只需要常數(shù)次操作即可完成塑崖，因?yàn)樗恍枰薷呐c該節(jié)點(diǎn)關(guān)聯(lián)的節(jié)點(diǎn)即可叠必，不需要檢查其他節(jié)點(diǎn)母怜，所以效率和查找類(lèi)似台丛。下面是2-3查找樹(shù)的效率：

5.3 平衡查找樹(shù)之紅黑樹(shù)（Red-Black Tree）

• 2-3查找樹(shù)能保證在插入元素之后能保持樹(shù)的平衡狀態(tài)，最壞情況下即所有的子節(jié)點(diǎn)都是2-node戴而，樹(shù)的高度為lgn凑术，從而保證了最壞情況下的時(shí)間復(fù)雜度。但是2-3樹(shù)實(shí)現(xiàn)起來(lái)比較復(fù)雜所意，于是就有了一種簡(jiǎn)單實(shí)現(xiàn)2-3樹(shù)的數(shù)據(jù)結(jié)構(gòu)淮逊，即紅黑樹(shù)（Red-Black Tree）。

• 基本思想：紅黑樹(shù)的思想就是對(duì)2-3查找樹(shù)進(jìn)行編碼扶踊，尤其是對(duì)2-3查找樹(shù)中的3-nodes節(jié)點(diǎn)添加額外的信息泄鹏。
  紅黑樹(shù)中將節(jié)點(diǎn)之間的鏈接分為兩種不同類(lèi)型:

  • 紅色鏈接，他用來(lái)鏈接兩個(gè)2-nodes節(jié)點(diǎn)來(lái)表示一個(gè)3-nodes節(jié)點(diǎn)秧耗。
  • 黑色鏈接用來(lái)鏈接普通的2-3節(jié)點(diǎn)命满。
  • 特別的，使用紅色鏈接的兩個(gè)2-nodes來(lái)表示一個(gè)3-nodes節(jié)點(diǎn)绣版，并且向左傾斜胶台，即一個(gè)2-node是另一個(gè)2-node的左子節(jié)點(diǎn)。這種做法的好處是查找的時(shí)候不用做任何修改杂抽，和普通的二叉查找樹(shù)相同诈唬。

• 紅黑樹(shù)的定義：
  紅黑樹(shù)是一種具有紅色和黑色鏈接的平衡查找樹(shù)，同時(shí)滿足：

  • 紅色節(jié)點(diǎn)向左傾斜
  • 一個(gè)節(jié)點(diǎn)不可能有兩個(gè)紅色鏈接
  • 整個(gè)樹(shù)完全黑色平衡缩麸，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上铸磅，黑色鏈接的個(gè)數(shù)都相同。

下圖可以看到紅黑樹(shù)其實(shí)是2-3樹(shù)的另外一種表現(xiàn)形式：如果我們將紅色的連線水平繪制杭朱，那么他鏈接的兩個(gè)2-node節(jié)點(diǎn)就是2-3樹(shù)中的一個(gè)3-node節(jié)點(diǎn)了阅仔。

• 紅黑樹(shù)的性質(zhì)：整個(gè)樹(shù)完全黑色平衡，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上弧械，黑色鏈接的個(gè)數(shù)都相同（2-3樹(shù)的第2）性質(zhì)八酒，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的距離都相等）。

• 復(fù)雜度分析：最壞的情況就是刃唐，紅黑樹(shù)中除了最左側(cè)路徑全部是由3-node節(jié)點(diǎn)組成羞迷，即紅黑相間的路徑長(zhǎng)度是全黑路徑長(zhǎng)度的2倍。

紅黑樹(shù)的平均高度大約為logn画饥。

紅黑樹(shù)這種數(shù)據(jù)結(jié)構(gòu)應(yīng)用十分廣泛衔瓮，在多種編程語(yǔ)言中被用作符號(hào)表的實(shí)現(xiàn)，如：
Java中的java.util.TreeMap,java.util.TreeSet抖甘；

5.4 B樹(shù)和B+樹(shù)（B Tree/B+ Tree）

平衡查找樹(shù)中的2-3樹(shù)以及其實(shí)現(xiàn)紅黑樹(shù)热鞍。2-3樹(shù)種，一個(gè)節(jié)點(diǎn)最多有2個(gè)key衔彻，而紅黑樹(shù)則使用染色的方式來(lái)標(biāo)識(shí)這兩個(gè)key薇宠。

維基百科對(duì)B樹(shù)的定義為“在計(jì)算機(jī)科學(xué)中，B樹(shù)（B-tree）是一種樹(shù)狀數(shù)據(jù)結(jié)構(gòu)米奸，它能夠存儲(chǔ)數(shù)據(jù)昼接、對(duì)其進(jìn)行排序并允許以O(shè)(log n)的時(shí)間復(fù)雜度運(yùn)行進(jìn)行查找、順序讀取悴晰、插入和刪除的數(shù)據(jù)結(jié)構(gòu)慢睡。B樹(shù)，概括來(lái)說(shuō)是一個(gè)節(jié)點(diǎn)可以擁有多于2個(gè)子節(jié)點(diǎn)的二叉查找樹(shù)铡溪。與自平衡二叉查找樹(shù)不同漂辐，B樹(shù)為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫(xiě)操作。B-tree算法減少定位記錄時(shí)所經(jīng)歷的中間過(guò)程棕硫，從而加快存取速度髓涯。普遍運(yùn)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)。

B樹(shù)定義：

B樹(shù)可以看作是對(duì)2-3查找樹(shù)的一種擴(kuò)展哈扮，即他允許每個(gè)節(jié)點(diǎn)有M-1個(gè)子節(jié)點(diǎn)纬纪。

• 根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)

• 每個(gè)節(jié)點(diǎn)有M-1個(gè)key蚓再，并且以升序排列

• 位于M-1和M key的子節(jié)點(diǎn)的值位于M-1 和M key對(duì)應(yīng)的Value之間

• 其它節(jié)點(diǎn)至少有M/2個(gè)子節(jié)點(diǎn)

下圖是一個(gè)M=4 階的B樹(shù):

B+樹(shù)定義：

B+樹(shù)是對(duì)B樹(shù)的一種變形樹(shù)，它與B樹(shù)的差異在于：

• 有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必然有k個(gè)關(guān)鍵碼包各；
• 非葉結(jié)點(diǎn)僅具有索引作用摘仅，跟記錄有關(guān)的信息均存放在葉結(jié)點(diǎn)中。
• 樹(shù)的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表问畅，可以按照關(guān)鍵碼排序的次序遍歷全部記錄娃属。

如下圖，是一個(gè)B+樹(shù):

• B+ 樹(shù)的優(yōu)點(diǎn)在于：
  • 由于B+樹(shù)在內(nèi)部節(jié)點(diǎn)上不好含數(shù)據(jù)信息护姆，因此在內(nèi)存頁(yè)中能夠存放更多的key矾端。 數(shù)據(jù)存放的更加緊密，具有更好的空間局部性卵皂。因此訪問(wèn)葉子幾點(diǎn)上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率秩铆。
  • B+樹(shù)的葉子結(jié)點(diǎn)都是相鏈的，因此對(duì)整棵樹(shù)的便利只需要一次線性遍歷葉子結(jié)點(diǎn)即可渐裂。而且由于數(shù)據(jù)順序排列并且相連豺旬，所以便于區(qū)間查找和搜索。而B(niǎo)樹(shù)則需要進(jìn)行每一層的遞歸遍歷柒凉。相鄰的元素可能在內(nèi)存中不相鄰族阅，所以緩存命中性沒(méi)有B+樹(shù)好。

但是B樹(shù)也有優(yōu)點(diǎn)膝捞，其優(yōu)點(diǎn)在于坦刀，由于B樹(shù)的每一個(gè)節(jié)點(diǎn)都包含key和value，因此經(jīng)常訪問(wèn)的元素可能離根節(jié)點(diǎn)更近蔬咬，因此訪問(wèn)也更迅速鲤遥。

下面是B 樹(shù)和B+樹(shù)的區(qū)別圖：

6. 分塊查找

分塊查找又稱(chēng)索引順序查找，它是順序查找的一種改進(jìn)方法林艘。
　　算法思想：將n個(gè)數(shù)據(jù)元素"按塊有序"劃分為m塊（m ≤ n）盖奈。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須"按塊有序"狐援；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字钢坦；而第2塊中任一元素又都必須小于第3塊中的任一元素，……
　　算法流程：
　　- step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表啥酱；
　　- step2 查找分兩個(gè)部分：先對(duì)索引表進(jìn)行二分查找或順序查找爹凹，以確定待查記錄在哪一塊中；然后镶殷，在已確定的塊中用順序法進(jìn)行查找禾酱。

7. 哈希查找

哈希表是一個(gè)在時(shí)間和空間上做出權(quán)衡的經(jīng)典例子。如果沒(méi)有內(nèi)存限制，那么可以直接將鍵作為數(shù)組的索引颤陶。那么所有的查找時(shí)間復(fù)雜度為O(1)颗管；如果沒(méi)有時(shí)間限制，那么我們可以使用無(wú)序數(shù)組并進(jìn)行順序查找指郁，這樣只需要很少的內(nèi)存忙上。哈希表使用了適度的時(shí)間和空間來(lái)在這兩個(gè)極端之間找到了平衡。只需要調(diào)整哈希函數(shù)算法即可在時(shí)間和空間上做出取舍闲坎。

Ref:
http://www.cnblogs.com/maybe2030/p/4715035.html