二叉平衡树

AVL树是带有平衡条件的二叉查找树，该平衡条件是每个节点的左子树和右子树的高度最多差1的二叉查找树。（空树的高度定义为-1。）

在该树上的所有操作的时间复杂度为O(logN)。插入过程中涉及到了单旋转和双旋转，具体实现请看。

B-树

阶为M的B-树是一棵有下列结构特性的树：

  • 树的根的儿子数在2和M之间。
  • 除根外，所有非树叶节点的儿子树在M/2（向上取整）和M之间。
  • 所有的树叶都在相同的深度上。
  • 每个节点存放至少2个，至多M个关键字。

B-树深度最多是logM/2(N)向上取整，Insert和Delete操作复杂度为O(MlogM(N))，Find操作复杂度为O(logN)。

B+树

B+树与B-树向比，增加了以下特性：

  • 非叶子结点的子树指针与关键字个数相同。每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
  • 为所有叶子结点增加一个链指针。
  • 所有关键字都在叶子结点出现。

MySQL数据库B-Tree索引

MySQL 聚集索引/非聚集索引简述
MyISAM和InnoDB的索引实现

参考

参考1
参考2
参考3
参考4《数据结构与算法分析：C语言描述》