JAVA

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

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

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

首先我們 插入 200，300，400，沒有什么問題，直接插入就好。

| 200 | 300 | 400 |

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

| 200 | 300 | 400 | 500 |

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

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

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

樹的高度h: 1， 2， 3 ， 4 ，.......... ， h

節(jié)點個數(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ù)庫索引結(jié)構(gòu)？

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

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

主存存取原理

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

圖5

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

主存的存取過程如下：

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

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

這里可以看出，主存存取的時間僅與存取次數(shù)呈線性關(guān)系，因為不存在機械操作，兩次存取的數(shù)據(jù)的“距離”不會對時間有任何影響，例如，先取A0再取A1和先取A0再取D3的時間消耗是一樣的。

磁盤存取原理

上文說過，索引一般以文件形式存儲在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機械運動耗費，因此磁盤I/O的時間消耗是巨大的。

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

圖6

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

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

圖7

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

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

局部性原理與磁盤預讀

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

當一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用。

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

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

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

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

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

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

每次新建節(jié)點時，直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現(xiàn)了一個node只需一次I/O。

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

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

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

上文還說過，B+Tree更適合外存索引，原因和內(nèi)節(jié)點出度d有關(guān)。從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于節(jié)點內(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é)點去掉了data域，因此可以擁有更大的出度，擁有更好的性能。

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

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

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

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

下面講具體的配置方法。

找到Tomcat的startup.sh文件，打開進行編輯。

在文件的開始位置，可以在一大堆注釋的后面，加入
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這個就是tomcat的安裝文件夾位置，不同的tomcat指定相應(yīng)的文件夾即可。

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

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

好了，解決了第一個問題，下面說第二個問題的解決方法。

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

現(xiàn)在進入Tomcat的bin文件夾，運行./startup.sh看看是不是可以啟動多個了。

很多tomcat進程退出（或者進程假死），都是由于頻繁的拋出OutOfMemeoryError導致的。

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

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

2、 重啟tomcat

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

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

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)]