建立了索引为什么能够增加效率，为什么主流数据库都使用b+树作为数据结构

面试 数据库

为什么是B树

为什么使用B+树?言简意赅，就是因为：
1. 文件很大，不可能全部存储在内存中，故要存储到磁盘上
2. 索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数(为什么使用B-/+Tree，还跟磁盘存取原理有关。)
3. 局部性原理与磁盘预读，预读的长度一般为页(page)的整倍数，(在许多操作系统中，页得大小通常为4k)
4. 数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远，无法利用局部性

数据库索引为什么会选择B树结构？
- 因为使用B树查找时，所用的磁盘IO操作次数比平衡二叉树更少，效率也更高。

为什么使用B树查找所用的磁盘IO操作次数比平衡二叉树更少？

1. 大规模数据存储中，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的高度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那么我们就需要减少树的高度以提高查找效率。而平衡多路查找树结构B树就满足这样的要求。B树的各种操作能使B树保持较低的高度，从而达到有效减少磁盘IO操作次数。

2. B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

B树结构

m阶B树
1. 树中每个结点最多有m棵子树
2. 若根节点不是叶子结点，则至少有2个子树
3. 除根节点外的所有非终端结点至少有 m/2 先上取整 棵子树
4. 每个非终端结点中包含信息(n,A0,K1,A1,K2,A2,,,,Kn,An)
Ki为关键字，按升序排序
指针Ai指向子树的根节点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1
关键字个数n满足 m/2 向上取整-1 <= n <= m-1
5. 所有叶子节点在同一层，不包含任何信息

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别

B树查找过程

B树的查找是如何实现的？
答：在给定的m阶B树中查找一个给定值v相等的关键字，必须从根结点开始进行查找。
B树应用于文件系统的动态索引结构，这些结点存储于外部存储设备上。当一个结点从外存调入内存后，我们可就这个结点的关键字序列，使用顺序查找（m较小时），或使用二分查找（ m较大时）。
假若当前被查找的结点中有j个关键字，那么，在查找等于给定值v的关键字时，会有如下可能：
（1）若v==ki (1≤i≤j)，则查找成功。
（2）若v < k1 ,则
① 如果p0为空，那么查找失败；
② 如果p0非空，那么从外存取得p0所指的结点，再继续进行查找。
（3）若ki
① 如果pi为空，那么查找失败；
② 如果pi非空，那么从外存取得pi所指的结点，再继续进行查找。
（4）若kj
① 如果pj为空，那么查找失败；
② 如果pj非空，那么从外存取得pj所指的结点，再继续进行查找。

既然查找效率与树的高度紧密相关，那么B树的高度由什么决定？
答：若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B树，其树高h至多为：
logt((n+1)/2)+1。
这里t是每个(除根外)内部结点的最小度数，即
t是每个(除根外)内部结点的最小度数，
B-树的高度为O(logtn)。

例子

给个B树性能分析具体例子呗？
答：首先须知：n个结点的二叉平衡的高度H（即lgn）比B树的高度h约大lgt倍，t为B树内部结点的最小度数ceil(m/2)。
【例】若阶m=1024，则lgt=lg512=9。此时若B树高度为4，则平衡的二叉排序树的高度约为36。显然，若m越大，则B树高度越小。
若要作为内存中的查找表，B树的表现还要比二叉平衡树好吗？
答：非也。若要作为内存中的查找表，B树却不一定比平衡的二叉排序树好，尤其当m较大时更是如此。
因为查找等操作的CPU计算时间在B树上是
O(mlogtn)=O(lgn·(m/lgt))
而m/lgt>1，所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此，仅在内存中使用的B树必须取较小的m。（通常取最小值m=3，此时B树中每个内部结点可以有2或3个孩子，这种3阶的B树称为2-3树）。