4.3 B樹 -> B+樹 -> B*樹：數(shù)據(jù)庫中的數(shù)據(jù)組織方式

????計算機中，為方便查找和定位，一般采用鍵值對（Key-Value Pair）的方式來描述，比如身份證、QQ號、學(xué)號和個人在相應(yīng)機構(gòu)的信息對應(yīng)等。我們知道2叉樹和N叉樹是等價的，很多算法只需要考慮簡單的2叉樹即可，但在有些具體問題上，直接考慮N叉樹會方便一些。但不受限的N叉樹不僅實現(xiàn)起來麻煩，節(jié)點分叉多又容易導(dǎo)致查找效率降低。所以由Rudolf Bayer和Edward M. McCreight提出了受限的N叉樹，即B樹。

B樹特征：

????1. 一節(jié)點可有多個鍵，具體限制在 [d,2d] 間，因此子節(jié)點數(shù)量在 [d+1,2d+1] 之間

????2. 根節(jié)點要有 2～2d 個子節(jié)點

????3. 各節(jié)點按大小按鍵分組，排列有序

????4. 經(jīng)過插入和刪除，某些節(jié)點不滿足2，3后，需要將小節(jié)點合并，或者拆分大節(jié)點

B+樹是B樹的變種，結(jié)構(gòu)干凈，便于一次訪問一大批數(shù)據(jù)：

????改進1：所有非葉節(jié)點只保留鍵，所有內(nèi)容保留在葉節(jié)點

????改進2：所有葉節(jié)點由一個指針串聯(lián)

B*樹是B+樹的再改進（Oracle數(shù)據(jù)庫采用）：

????改進1：在B+樹的內(nèi)部（非根，非葉節(jié)點）節(jié)點間增加指向兄弟節(jié)點的指針

????改進2：調(diào)整合并和拆分節(jié)點機制，減少樹中空間浪費

????當(dāng)然，如果數(shù)據(jù)的訪問方式不是按照事先設(shè)定好的鍵進行，而是根據(jù)事物中的某一項內(nèi)容，比如學(xué)校中20～21歲的學(xué)生，那就需要數(shù)據(jù)庫建立很多用哈希表實現(xiàn)的【索引】。

4.4 卡特蘭數(shù)

????滿二叉樹就是二叉樹中節(jié)點度為0或2的樹（注意與完全二叉樹的區(qū)分）?，F(xiàn)發(fā)現(xiàn)葉節(jié)點N=1或2時，都只有一種滿二叉樹，N=3，4時，則分別有2種和5種滿二叉樹，問N=6,7...時的情況？

????這題正向思考找規(guī)律很難，需用逆向思考-遞歸，然后累加：

????解析解是這個（過程略，組合數(shù)學(xué)母函數(shù)或通信中卷積），最早由數(shù)學(xué)家Catalan發(fā)現(xiàn)，其C(N)定義和這里S(N)式子相差1，可以將卡特蘭數(shù)C(N)理解成葉子節(jié)點數(shù)量為N+1的滿二叉樹的數(shù)量：

????卡特蘭數(shù)問題有很多等價問題，遇到時可以相互轉(zhuǎn)化：

????1. 凸多邊形的劃分問題：

????解：三角形，矩形和五邊形的方法數(shù)分別對應(yīng)卡特蘭數(shù)C(1), C(2), C(3)，凸N邊型對應(yīng)C(N-2)，可用遞歸方式證明。選定一條邊做底邊，該底邊可與其他任意未使用頂點構(gòu)成一個三角形，以7邊形為例，如圖：

????將凸N邊形頂點從1～N編號，選定的底邊和k頂點（k可取2,3,...k-1等k-2種情況）構(gòu)成的三角形將其分成左右兩獨立部分，假定k邊形有P(k)種劃分三角形的方法，P(2)=1, P(3)=1?？傻眠f推公式：

????簡單變換后可得卡特蘭數(shù)?P(N) = C(N-2)。

????2. N個字符的字符串合并問題：C(N-1)

????3. 街區(qū)走法：

????4. 力扣題96：

????卡特蘭數(shù)會出現(xiàn)在很多地方，包括自然語言處理中，一個句子的句法分析等，在這里，卡特蘭數(shù)就是一個句子可以對應(yīng)的語法樹的數(shù)量上限，因為C(N)是指數(shù)函數(shù)，所以句法分析非常困難，需要使用一些語法規(guī)則作為限制或剪枝條件，當(dāng)然這里主要還是一個【等價】的思想更加重要一些：