哈希表

key-value格式，通过key可以计算出具体的index值，但是可能会冲突，冲突就需要拉链，类似java的HashMap
优点：进行等值查询时快
缺点：进行范围查询时慢（因为字段值的存储是无序的，写入顺序是有序的，顺序写的效率大于随机写），因此进行范围查询需要扫描全表
适用场景：等值查询，如MemoryCache及一些其他NoSQL的引擎，与等值查询对应的范围查询、模糊查询

有序数组

优点：通过名称就可以了解到有序数组弥补了哈希表在范围查找方面的不足，同时又因为是有序的，因此做等值查询时，通过二分查找也不会很慢，时间复杂度为O(logn)
缺点：插入数据时，如果不是尾部追加，就需要挪动后面所有的记录，成本太高，更新也类似
适用场景：适用于静态存储引擎，比如归档信息保留

搜索树

二叉树

父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值，查找的时间复杂度正常情况下为O(logn)
优点：
缺点：

  1. 极端情况下会退化为链表，时间复杂度变为0(n)

  2. 索引不止存在于内存中，还要写到磁盘上，如果树过高，每次查询都需要访问过多节点，即访问数据块过多，IO次数越多，性能越差

    自平衡二叉树（AVL二叉树）：

    树不至于退化成链表，人们发明了AVL数（平衡二叉搜索树）：任何节点的左子树和右子树高度最多相差1

    多叉树

    多叉树就是节点可以是M个，能有效地减少高度，高度变小后，I/O自然就少了，性能比二叉树就好多了

    B树

    简单的说就是多叉树，每个节点会存储数据，和指向下一个节点的指针

    B+树（InnoDB引擎）

    B树的改进版，只有叶子节点才存数据，非叶子节点是存储的指针；所有的叶子节点构成一个有序链表，每个叶子结点都是一个页，每次新建节点的时候就会申请一个页空间
    优点：

  3. 使用双向链表串联所有叶子节点，区间查询效率更高，因为所有数据都在B+树的叶子节点，但是B树则需要通过中序遍历才能完成范围查询的查找。

  4. B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，这样就会造成查询的效率的不稳定
  5. B+树的查询效率更高，因为B+树更矮更胖，高度小，查询产生的I/O最少