数据库索引为什么会选择B树结构

B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，

一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，

也可能是一个包含两个或两个以上孩子节点的节点。

B+ 树通常用于数据库和 *** 作系统的文件系统中。

NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。

B+ 树的特点是能够保持数据稳定有序，

其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

B 树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。

B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：树中每个结点最多含有m个孩子（m>=2）；除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：

a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)<Ki。

b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。

c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

---