有序数组

数组是一种重要的数据结构，有序数组顾名思义，key是递增的，很适合等值和范围查询。

id      1   2   3   4 ....   n
name    a   b	c   d        n

假设id没有重复那么拿取id对应的name用二分法就可以实现，时间复杂度是O(logn)。优点很明显，但是缺点也很显然，如有数据的新增则需要数据移动（新申请空间、拷贝数据和释放空间等动作）

Hash

哈希表是一种以键值对（K-V）储存数据的结构，就如java中的hashmap，通过key可以get对应的value。哈希的思路是用特定的哈希函数将 K 换算到数组中的位置，然后将值 V 放到数组的这个位置。如果遇到不同的 K 计算出相同的位置，则在这个位置拉出一个链表依次存放。但是hash表支持范围查询吗？

二叉搜索树

二叉树的特点：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
   3.任意节点的左、右子树也分别为二叉查找树；
   二叉树的优势是查找和插入的时间复杂度较低
   
   比如我要找5，我们只需要三次就能检索到，我们要找大于5的只需要取父节点6的右子节点就可以。
   但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 O（N），检索性能急剧下降。
   
   当然二叉树后续又衍生出了AVL树和红黑树。

B+树

B+树可以理解为N叉树和有序数组的结合体。

优点：
1.层级更低，IO 次数更少（数据库的瓶颈在于磁盘IO，层级越多磁盘IO就越多。每层拿取数据再加载到内存里，这个操作是很费时的，假如我有1000层，10000层）
2.每次都需要查询到叶子节点，查询性能稳定
3.叶子节点形成有序链表，范围查询方便