数据结构：B树与B+树
工具
数据结构与算法可视化在线演示
m阶 B树有以下特点：
B-树，有时又写为B_树（其中的-或者_只是连字符，并不读作 B减树），一颗 m 阶(或度)的 B-树，或者本身是空树，否则必须满足以下特性：
-
结点点数量要求：除根结点之外，所有非叶子结点的子树数在[2,m]区间，即：
- 树中每个结点至多有 m 棵子树；
- 若根结点不是叶子结点，则至少有两棵子树；
-
结点半满要求：除根之外的所有非叶子结点至少有
⌈m/2⌉棵子树，要求结点半满，保证B树不会退化成简单地二叉树； -
结点中关键字数要求：有n个子结点的非叶子结点恰好包含有n-1个关键字，（数量关系犹如
一个西瓜切两半，只需要关键的一刀,一分为二），取值范围是：⌈m/2⌉-1≤ n ≤m-1，
| 数据项 | P 0 P_0 P0 | K 1 K_1 K1 | P 1 P_1 P1 | K 2 K_2 K2 | P 2 P_2 P2 | … | … | K n K_n Kn | P n P_n Pn |
|---|---|---|---|---|---|---|---|---|---|
| 描述 | 指针 | 关键字 1 | 指针 | 关键字 2 | 指针 | … | … | 关键字 n | 指针 |
P 0 P_0 P0， K 1 K_1 K1， P 1 P_1 P1， K 2 K_2 K2， P 2 P_2 P2，…， P n P_n Pn， K n K_n Kn
- K i K_i Ki （i 从 1 到 n）为关键字，且 K i K_i Ki < K i + 1 K_{i+1} Ki+1 ；
-
P
i
P_i
Pi 代表指向子树根结点的指针，且:
- 指针 P i − 1 P_{i-1} Pi−1 所指的子树中所有结点的关键字都小于 K i K_i Ki，
- P n P_n Pn 所指子树中所有的结点的关键字都大于 K n K_n Kn。
B+树的特点
m阶 B+树有以下特点（基于 B 树的改版）：
- 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有的叶子结点在相同的深度上，时间复杂度 O ( l o g n ) O(log^n) O(logn)
- 数据项存储在树叶上，也就是存储在叶子结点上。
- 非叶子结点存储直到
m-1个关键字以指示搜索的方向,且关键字 K i K_i Ki < K i + 1 K_{i+1} Ki+1 ；
