运行时间计算常用计算法则：

如果一个算案发用常数时间(O(1))将问题的大小削减为其一部分（通常是1/2），那么该算法就是(O(log N))。另一方面如果使用常数时间只是把问题减少一个常数的数数量（如将问题减少1），那么这种算法就是O(N)的。

树

基本概念

一棵树存在N个节点和N-1条边

从节点$n_1$到$n_k$的路径为节点$n_1$、$n_2$…$n_k$的一个序列，这条路劲的长为该路径上的边的条数，即$k-1$。

对于任意节点$n_i$，$n_i$的深度为从根到$n_i$的唯一路径的长，因此根的深度为0。$n_i$的高是从$n_i$到一篇树叶的最长路径的长，因此所有树叶的高都是0.

AVL树

特性

任意一个节点的左右子树的高度必须相同

$B^+$树

特性

  1. 数据像存储在树叶上。
  2. 非叶子节点存储$M-1$个关键字；关键字$i$代表子树$i+1$种的最小的关键字
  3. 树的根或者树叶，其子节点数在2~M之间。
  4. 除根外，所有非树叶节点的子节点数在$\lceil M/2 \rceil$和$M$之间
  5. 所有的树叶都在相同的深度上，并由$\lceil L/2 \rceil$和$L$之间个数据项

M代表$B^+$树的阶，表示非叶子节点最多有$M-1$个关键字，$M$个子节点