应用场景——索引

关系型数据库中，索引大多采用B/B+树来作为存储结构，而全文搜索引擎的索引则主要采用hash的存储结构，这两种数据结构有什么区别？

范围查询和模糊查询，哈希索引不适用。

为什么会有B树？

我们假设我们的数据量达到了亿级别，主存当中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 I/O 操作相当耗时，而提出 B-树的主要目的就是减少磁盘的 I/O 操作。大多数平衡树的操作（查找、插入、删除，最大值、最小值等等）需要O(h)次磁盘访问操作，其中h是树的高度。但是对于 B-树而言，树的高度将不再是O(logN)，而是一个可控的高度h。

B树

B-树是一种平衡的多叉查找树，注意： B树就是B-树，"-"是个连字符号，不是减号。

一颗m阶的B树定义如下：
1）每个结点最多有m-1个关键字。
2）根结点最少可以只有1个关键字。
3）非根结点至少有Math.ceil(m/2)-1个关键字。
4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

B+树

B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互链接。

一棵m阶的B+树主要有这些特点：
1）有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2）所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3）所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B树和B+树的区别

B+树和B-树的主要区别如下：
1）B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
2）B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
3）B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。

总结

1.索引为排好序的一种数据结构，用于提升数据库的查找速度。
2.Hash索引时间复杂度为O(1)，树索引是O(log(n))。Hash 底层是哈希表实现，等值查询，可以快速定位数据。但不支持范围查询，无法用于排序分组，无法模糊查询等操作。
3.B+树作为索引优势：
叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；
非叶子节点存储记录的PK（KEY数据小，相同内存情况下，节点可以多存KEY，增大了节点广度(B+树出度更大，进而树高更矮，磁盘IO次数更少)）用于查询加速，适合内存存储；
叶子之间，增加了链表。可以很好的支持范围查询，并且获取所有节点，不再需要中序遍历；
更少查询次数：B+树出度更大，树高更低，查询次数更少；
很适合磁盘存储，能够充分利用局部性原理，磁盘预读（为了减少IO操作，往往不严格按需读取，而是预读。B+树叶子结点存储相临，读取会快一些）