4.3 B树 -> B+树 -> B*树：数据库中的数据组织方式

    计算机中，为方便查找和定位，一般采用键值对（Key-Value Pair）的方式来描述，比如身份证、QQ号、学号和个人在相应机构的信息对应等。我们知道2叉树和N叉树是等价的，很多算法只需要考虑简单的2叉树即可，但在有些具体问题上，直接考虑N叉树会方便一些。但不受限的N叉树不仅实现起来麻烦，节点分叉多又容易导致查找效率降低。所以由Rudolf Bayer和Edward M. McCreight提出了受限的N叉树，即B树。

B树特征：

    1. 一节点可有多个键，具体限制在 [d,2d] 间，因此子节点数量在 [d+1,2d+1] 之间

    2. 根节点要有 2～2d 个子节点

    3. 各节点按大小按键分组，排列有序

    4. 经过插入和删除，某些节点不满足2，3后，需要将小节点合并，或者拆分大节点

B+树是B树的变种，结构干净，便于一次访问一大批数据：

    改进1：所有非叶节点只保留键，所有内容保留在叶节点

    改进2：所有叶节点由一个指针串联

B*树是B+树的再改进（Oracle数据库采用）：

    改进1：在B+树的内部（非根，非叶节点）节点间增加指向兄弟节点的指针

    改进2：调整合并和拆分节点机制，减少树中空间浪费

    当然，如果数据的访问方式不是按照事先设定好的键进行，而是根据事物中的某一项内容，比如学校中20～21岁的学生，那就需要数据库建立很多用哈希表实现的【索引】。

4.4 卡特兰数

    满二叉树就是二叉树中节点度为0或2的树（注意与完全二叉树的区分）。现发现叶节点N=1或2时，都只有一种满二叉树，N=3，4时，则分别有2种和5种满二叉树，问N=6,7...时的情况？

    这题正向思考找规律很难，需用逆向思考-递归，然后累加：

    解析解是这个（过程略，组合数学母函数或通信中卷积），最早由数学家Catalan发现，其C(N)定义和这里S(N)式子相差1，可以将卡特兰数C(N)理解成叶子节点数量为N+1的满二叉树的数量：

    卡特兰数问题有很多等价问题，遇到时可以相互转化：

    1. 凸多边形的划分问题：

    解：三角形，矩形和五边形的方法数分别对应卡特兰数C(1), C(2), C(3)，凸N边型对应C(N-2)，可用递归方式证明。选定一条边做底边，该底边可与其他任意未使用顶点构成一个三角形，以7边形为例，如图：

    将凸N边形顶点从1～N编号，选定的底边和k顶点（k可取2,3,...k-1等k-2种情况）构成的三角形将其分成左右两独立部分，假定k边形有P(k)种划分三角形的方法，P(2)=1, P(3)=1。可得递推公式：

    简单变换后可得卡特兰数 P(N) = C(N-2)。

    2. N个字符的字符串合并问题：C(N-1)

    3. 街区走法：

    4. 力扣题96：

    卡特兰数会出现在很多地方，包括自然语言处理中，一个句子的句法分析等，在这里，卡特兰数就是一个句子可以对应的语法树的数量上限，因为C(N)是指数函数，所以句法分析非常困难，需要使用一些语法规则作为限制或剪枝条件，当然这里主要还是一个【等价】的思想更加重要一些：