JAVA

首先我們介紹一下一顆 m 階B-tree的特性，那么這個(gè) m 階是怎么定義的呢？這里我們以一個(gè)節(jié)點(diǎn)能擁有的最大子節(jié)點(diǎn)數(shù)來(lái)表示這顆樹(shù)的階數(shù)。舉個(gè)例子，如果一個(gè)節(jié)點(diǎn)最多有 n 個(gè)key，那么這個(gè)節(jié)點(diǎn)最多就會(huì)有 n+1 個(gè)子節(jié)點(diǎn)，這棵樹(shù)就叫做 n+1（m=n+1）階樹(shù)。一顆 m 階B-tree包括以下5條特性：

1. 每個(gè)節(jié)點(diǎn)最多有 m 個(gè)子節(jié)點(diǎn)
2. 除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)，其它每個(gè)節(jié)點(diǎn)至少有 [m/2] （向上取整的意思）個(gè)子節(jié)點(diǎn)
3. 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則其至少有2個(gè)子節(jié)點(diǎn)
4. 所有NULL節(jié)點(diǎn)到根節(jié)點(diǎn)的高度都一樣
5. 除根節(jié)點(diǎn)外，其它節(jié)點(diǎn)都包含 n 個(gè)key，其中 [m/2] -1 <= n <= m-1

這些特性可能看著不太好理解，下面我們會(huì)介紹B-tree的插入，在插入節(jié)點(diǎn)的過(guò)程中我們就會(huì)慢慢理解這些特性了。B-tree的插入比較簡(jiǎn)單，就是一個(gè)節(jié)點(diǎn)至下而上的分裂過(guò)程。下面我們具體以一顆4階樹(shù)來(lái)展示B-tree的插入過(guò)程。

首先我們 插入 200，300，400，沒(méi)有什么問(wèn)題，直接插入就好。

| 200 | 300 | 400 |

現(xiàn)在我們接著插入500，這個(gè)時(shí)候我們發(fā)現(xiàn)有點(diǎn)問(wèn)題，根據(jù)定義及特性1我們知道一顆4階B-tree的每個(gè)節(jié)點(diǎn)最多只能有3個(gè)key，插入500后這個(gè)節(jié)點(diǎn)就有4個(gè)key了。

| 200 | 300 | 400 | 500 |

這個(gè)時(shí)候我們就需要分裂，將中間的key上移到父節(jié)點(diǎn)，左邊的作為左節(jié)點(diǎn)，右邊的作為右節(jié)點(diǎn)，如下圖所示：

通過(guò)整個(gè)的插入過(guò)程我們也會(huì)發(fā)現(xiàn)，B-tree和二叉樹(shù)的一個(gè)顯著的區(qū)別就是，B-tree是從下往上生長(zhǎng)，而二叉樹(shù)是從上往下生長(zhǎng)的。現(xiàn)在我們想想特性2和特性5是為什么？首先我們知道子節(jié)點(diǎn)的個(gè)數(shù)是等于key的數(shù)目+1，然后一個(gè)節(jié)點(diǎn)達(dá)到m個(gè)key后就會(huì)分裂，所以分裂后的節(jié)點(diǎn)最少能得到 m/2 - 1個(gè)key 。為啥還要減一呢？因?yàn)檫€要拿一個(gè)作為父節(jié)點(diǎn)。所以這個(gè)節(jié)點(diǎn)最少回?fù)碛?m/2 - 1 + 1 = m/2 個(gè)子節(jié)點(diǎn)。同樣得到特性5，因?yàn)樽钌儆衜/2個(gè)子節(jié)點(diǎn)，所以最少就含有m/2-1個(gè)key，m 階樹(shù)，每個(gè)節(jié)點(diǎn)存到了m個(gè)key就會(huì)分裂，所以最多就有 m-1個(gè)key。

根據(jù)以上特性我們能推出一棵含有N個(gè)總關(guān)鍵字?jǐn)?shù)的m階的B-tree樹(shù)的最大高度h的值,

樹(shù)的高度h: 1， 2， 3 ， 4 ，.......... ， h

節(jié)點(diǎn)個(gè)數(shù)s: 1， 2， 2*(m/2)， 2*(m/2)(m/2)， ........ ，2*(m/2)的h-2次方

s = 1 + 2(1 - )/(1- (m/2))

N = 1 + s * ((m/2) - 1) = 2 * () - 1

h = log┌m/2┐((N+1)/2 )+1

2：為什么btree/b+tree 為常用數(shù)據(jù)庫(kù)索引結(jié)構(gòu)？

上文說(shuō)過(guò)，紅黑樹(shù)等數(shù)據(jù)結(jié)構(gòu)也可以用來(lái)實(shí)現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)普遍采用B-/+Tree作為索引結(jié)構(gòu)，這一節(jié)將結(jié)合計(jì)算機(jī)組成原理相關(guān)知識(shí)討論B-/+Tree作為索引的理論基礎(chǔ)。

一般來(lái)說(shuō)，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤上。這樣的話，索引查找過(guò)程中就要產(chǎn)生磁盤I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說(shuō)，索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤I/O的存取次數(shù)。下面先介紹內(nèi)存和磁盤存取原理，然后再結(jié)合這些原理分析B-/+Tree作為索引的效率。

主存存取原理

目前計(jì)算機(jī)使用的主存基本都是隨機(jī)讀寫存儲(chǔ)器（RAM），現(xiàn)代RAM的結(jié)構(gòu)和存取原理比較復(fù)雜，這里本文拋卻具體差別，抽象出一個(gè)十分簡(jiǎn)單的存取模型來(lái)說(shuō)明RAM的工作原理。

圖5

從抽象角度看，主存是一系列的存儲(chǔ)單元組成的矩陣，每個(gè)存儲(chǔ)單元存儲(chǔ)固定大小的數(shù)據(jù)。每個(gè)存儲(chǔ)單元有唯一的地址，現(xiàn)代主存的編址規(guī)則比較復(fù)雜，這里將其簡(jiǎn)化成一個(gè)二維地址：通過(guò)一個(gè)行地址和一個(gè)列地址可以唯一定位到一個(gè)存儲(chǔ)單元。圖5展示了一個(gè)4 x 4的主存模型。

主存的存取過(guò)程如下：

當(dāng)系統(tǒng)需要讀取主存時(shí)，則將地址信號(hào)放到地址總線上傳給主存，主存讀到地址信號(hào)后，解析信號(hào)并定位到指定存儲(chǔ)單元，然后將此存儲(chǔ)單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取。

寫主存的過(guò)程類似，系統(tǒng)將要寫入單元地址和數(shù)據(jù)分別放在地址總線和數(shù)據(jù)總線上，主存讀取兩個(gè)總線的內(nèi)容，做相應(yīng)的寫操作。

這里可以看出，主存存取的時(shí)間僅與存取次數(shù)呈線性關(guān)系，因?yàn)椴淮嬖跈C(jī)械操作，兩次存取的數(shù)據(jù)的“距離”不會(huì)對(duì)時(shí)間有任何影響，例如，先取A0再取A1和先取A0再取D3的時(shí)間消耗是一樣的。

磁盤存取原理

上文說(shuō)過(guò)，索引一般以文件形式存儲(chǔ)在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機(jī)械運(yùn)動(dòng)耗費(fèi)，因此磁盤I/O的時(shí)間消耗是巨大的。

圖6是磁盤的整體結(jié)構(gòu)示意圖。

圖6

一個(gè)磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉(zhuǎn)動(dòng)（各個(gè)磁盤必須同步轉(zhuǎn)動(dòng)）。在磁盤的一側(cè)有磁頭支架，磁頭支架固定了一組磁頭，每個(gè)磁頭負(fù)責(zé)存取一個(gè)磁盤的內(nèi)容。磁頭不能轉(zhuǎn)動(dòng)，但是可以沿磁盤半徑方向運(yùn)動(dòng)（實(shí)際是斜切向運(yùn)動(dòng)），每個(gè)磁頭同一時(shí)刻也必須是同軸的，即從正上方向下看，所有磁頭任何時(shí)候都是重疊的（不過(guò)目前已經(jīng)有多磁頭獨(dú)立技術(shù)，可不受此限制）。

圖7是磁盤結(jié)構(gòu)的示意圖。

圖7

盤片被劃分成一系列同心環(huán)，圓心是盤片中心，每個(gè)同心環(huán)叫做一個(gè)磁道，所有半徑相同的磁道組成一個(gè)柱面。磁道被沿半徑線劃分成一個(gè)個(gè)小的段，每個(gè)段叫做一個(gè)扇區(qū)，每個(gè)扇區(qū)是磁盤的最小存儲(chǔ)單元。為了簡(jiǎn)單起見(jiàn)，我們下面假設(shè)磁盤只有一個(gè)盤片和一個(gè)磁頭。

當(dāng)需要從磁盤讀取數(shù)據(jù)時(shí)，系統(tǒng)會(huì)將數(shù)據(jù)邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個(gè)磁道，哪個(gè)扇區(qū)。為了讀取這個(gè)扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個(gè)扇區(qū)上方，為了實(shí)現(xiàn)這一點(diǎn)，磁頭需要移動(dòng)對(duì)準(zhǔn)相應(yīng)磁道，這個(gè)過(guò)程叫做尋道，所耗費(fèi)時(shí)間叫做尋道時(shí)間，然后磁盤旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過(guò)程耗費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間。

局部性原理與磁盤預(yù)讀

由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：

當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。

程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。

由于磁盤順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高I/O效率。

預(yù)讀的長(zhǎng)度一般為頁(yè)（page）的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)（在許多操作系統(tǒng)中，頁(yè)得大小通常為4k），主存和磁盤以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤發(fā)出讀盤信號(hào)，磁盤會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行。

B-/+Tree索引的性能分析

到這里終于可以分析B-/+Tree索引的性能了。

上文說(shuō)過(guò)一般使用磁盤I/O次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣。先從B-Tree分析，根據(jù)B-Tree的定義，可知檢索一次最多需要訪問(wèn)h個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B- Tree還需要使用如下技巧：

每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過(guò)100，因此h非常小（通常不超過(guò)3）。

綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。

而紅黑樹(shù)這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無(wú)法利用局部性，所以紅黑樹(shù)的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。

上文還說(shuō)過(guò)，B+Tree更適合外存索引，原因和內(nèi)節(jié)點(diǎn)出度d有關(guān)。從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于節(jié)點(diǎn)內(nèi)key和data的大小：

dmax = floor(pagesize / (keysize + datasize + pointsize))  (pagesize – dmax >= pointsize)

或

dmax = floor(pagesize / (keysize + datasize + pointsize)) - 1  (pagesize – dmax < pointsize)

floor表示向下取整。由于B+Tree內(nèi)節(jié)點(diǎn)去掉了data域，因此可以擁有更大的出度，擁有更好的性能。

這一章從理論角度討論了與索引相關(guān)的數(shù)據(jù)結(jié)構(gòu)與算法問(wèn)題，下一章將討論B+Tree是如何具體實(shí)現(xiàn)為MySQL中索引，同時(shí)將結(jié)合MyISAM和InnDB存儲(chǔ)引擎介紹非聚集索引和聚集索引兩種不同的索引實(shí)現(xiàn)形式。

1、不同的tomcat的啟動(dòng)文件startup.sh 中要指定各自的CATALINA_HOME和CATALINA_BASE這兩個(gè)環(huán)境變量。

2、不同的tomcat啟動(dòng)和關(guān)閉監(jiān)聽(tīng)不同的端口

很多人喜歡把CATALINA_HOME和CATALINA_BASE配置到系統(tǒng)環(huán)境變量中去，我們不這么做，我們要做的只是把JDK及CLASSPATH配置到環(huán)境變量中去即可，因?yàn)檫@個(gè)可以通用。
CATALINA_HOME和CATALINA_BASE的區(qū)別。簡(jiǎn)單的說(shuō)，CATALINA_HOME是Tomcat的安裝目 錄，CATALINA_BASE是Tomcat的工作目錄。如果我們想要運(yùn)行Tomcat的 多個(gè)實(shí)例，但是不想安裝多個(gè)Tomcat軟件副本。那么我們可以配置多個(gè)工作 目錄，每個(gè)運(yùn)行實(shí)例獨(dú)占一個(gè)工作目錄，但是共享同一個(gè)安裝目錄

下面講具體的配置方法。

找到Tomcat的startup.sh文件，打開(kāi)進(jìn)行編輯。

在文件的開(kāi)始位置，可以在一大堆注釋的后面，加入
export CATALINA_BASE=/usr/ratest/apache-tomcat-7.0.16
export CATALINA_HOME=/usr/ratest/apache-tomcat-7.0.16

/usr/ratest/apache-tomcat-7.0.16這個(gè)就是tomcat的安裝文件夾位置，不同的tomcat指定相應(yīng)的文件夾即可。

注意，這兩句話一定要在exec “$PRGDIR”/”$EXECUTABLE” start “$@”這句話的前面，我們放在文件的開(kāi)始位置了，所以，就可以不考慮了。

然后就是要修改shutdown.sh文件，同樣在頭部加入上面的兩行即可，也要在exec “$PRGDIR”/”$EXECUTABLE” stop “$@”的前面。

好了，解決了第一個(gè)問(wèn)題，下面說(shuō)第二個(gè)問(wèn)題的解決方法。

找到并打開(kāi)server.xml文件，里面有諸如8080，8009，8443等等端口配置，統(tǒng)一給這些數(shù)字加上100，或者1000或者其他什么數(shù)字，只要是不跟其他Tomcat或者當(dāng)前l(fā)inux上其他服務(wù)的端口重復(fù)即可。

現(xiàn)在進(jìn)入Tomcat的bin文件夾，運(yùn)行./startup.sh看看是不是可以啟動(dòng)多個(gè)了。

很多tomcat進(jìn)程退出（或者進(jìn)程假死），都是由于頻繁的拋出OutOfMemeoryError導(dǎo)致的。

為了讓tomcat退出前或者發(fā)生OutOfMemeoryError時(shí)自動(dòng)dump堆棧信息，方便事后排查問(wèn)題，我們可以做如下操作：

1、 在tomcat啟動(dòng)參數(shù)中加入兩個(gè)參數(shù) -XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=/export/home/tomcat/domains/server2/oom.hprof

2、 重啟tomcat

參數(shù)說(shuō)明
（1）-XX:+HeapDumpOnOutOfMemoryError 表示當(dāng)JVM發(fā)生OOM時(shí)，自動(dòng)生成DUMP文件。
（2）-XX:HeapDumpPath=存儲(chǔ)文件/目錄 表示生成DUMP文件的路徑

想從JAVA轉(zhuǎn)到obj-c，看了些基礎(chǔ)的東西，感覺(jué)很奇怪，可能不太習(xí)慣，在網(wǎng)上看到一個(gè)不錯(cuò)文章有助理解obj-c的一些核心機(jī)制。

SomeClass.h
@interface SomeClass : NSObject{
}
-(void) print;
@end 

#import "SomeClass.h"
 
@interface SomeClass (Hello)
-(void)hello;
@end

#import "SomeClass+Hello.h"
@implementationSomeClass (Hello)
-(void)hello{
    NSLog (@"name：%@ ", @"Jacky");
}
@end 

#import "SomeClass+Hello.h"
 
SomeClass * sc =[[SomeClass alloc] init];
[sc hello] 

@protocol ProcessDataDelegate <NSObject>
@required
- (void) processSuccessful: (BOOL)success;

@optional
- (id) submitOrder: (NSNumber *) orderid;
@end

@interface TestAppDelegate : NSObject<ProcessDataDelegate>;

@end

@implementation TestAppDelegate

- (void) processSuccessful: (BOOL)success{
    if (success) {
        NSLog(@"成功");
    }else {
        NSLog(@"失敗");
    }
}

@end 

@protocol A
     -(void)methodA;
@end
@protocol B <A>
     -(void)methodB;
@end

[obj conformsToProtocol:@protocol(ProcessDataDelegate)]