数组

存储结构：需要一块连续且固定大小的物理内存。
查询方式：只要知道数组下标，就可以直接根据当前数组指针+下标offset定位到具体的内存地址，所以随机读查询的时间复杂度是O(1)。
结构变更：如果是对中间下标进行增删，由于为了保证数组的连续性，需要对增删操作的后续所有下标进行移动。此外因为内存是连续且固定大小，所以数组的长度变更如果超出固定大小就需要重新申请内存并迁移数据（我们之所以在使用数组的时候感觉可以随便add是因为要么没超过预申请的内存大小，要么语言内部实现了扩容机制，如Java的List）。
其他：无需要求节点有序

链表

存储结构：无需内存连续来存储对象，但数据结构内部需要一个指针指向下一个/前一个对象。
查询方式：顺序查找，从头开始遍历，时间复杂度是O(n)。
结构变更：不管在什么位置变更，只需要将前节点的指针指向当前节点，当前节点指向原下一个节点即可完成节点新增，删除直接将上节点的指针指向下节点即可。无需扩容机制。
其他：无需要求节点有序

跳跃表

由于链表的结构变更机制优秀，查询性能相对较差，所以需要进行一定的优化，这就是跳跃表。
但是要注意的是跳跃表的前提是有序链表，这点和普通链表是不一样的，也就是它的适用范围更严格。
跳跃表可以总结为链表节点的多级索引，其实和B树是非常相似的结构，首先要求最底层（B树叫叶子节点）链表就是原始链表（或者说有完整的节点数据）。在此基础上进行分段，理论上分的越均匀性能越好。经过论证，最佳查询效率是O(log2N)，我们也可以以此来确定分层数。
但Redis采用是随机方式（非常的玄学）来选择跳跃范围，每一级的随机范围不同，产出不同的索引层级。

树

二叉树

一颗为空或者非叶子节点最多有两个子节点的树结构。注意的是二叉树本身定义非常基础，既没有顺序关系，也没有大小关系，你可以认为是一个abstract版本的接口定义，没有实用意义，所有有实用意义的都需要在其基础上升级。

二叉搜索树（BST）

基于二分法的思想（有序，log2N），需要一种天然适合二分查找的数据结构，然后需要遵循左小右大的逻辑，形成一颗类似树的结构，就是二叉搜索树。
如果只有左小右大原则，不能解决隔代无序的问题，所以BST还要求根节点左边任意节点都小于它，右边都大于它。且任意一个非叶子节点作为根节点也都是一颗BST。

平衡二叉树（AVL）

二叉树的查询效率和树高度存在反比关系：高度越高效率越低，高度越低效率越高。本质上理解高度越平衡，单次下溯后丢弃掉的非目标数据越多。
由于这个关系以及BST会存在高度问题，也就是如果1-10数组以1为根节点，那么从上到下都是右叉节点，形成了一条链表，相应低查询性能也退化为O(N)，如何解决这个问题，就演化出了平衡二叉树，要去两边高度差不超过1，简单理解上就是换一个中间节点，比如1-10数组以5/6为根节点即可。

红黑树

相对于AVL追求绝对平衡带来的较高旋转成本，红黑树通过适当降低平衡要求（平衡因子可选范围更大），来降低旋转成本，这也是Java的hashmap为什么用红黑树而不用AVL树的原因。
但也不是说红黑树就优于AVL，AVL的绝对平衡带来了查询效率的稳定，即log2N。而红黑树在不能保证这一点，所以这就是一种妥协，在写入性能和查询性能之间的权衡。

B树&B+树

B树和跳跃表的区别在于，跳跃表的最小存储对象可以细化到单个对象，所以其复杂度为可以为log2N，而Mysql的InnoDB存储引擎的最小存储单元是页，一页一般有16K大小，考虑一般单个索引的大小在十几B左右，所以一页可以存储几百上千个索引，就是说你可以理解为均分范围为1000跳跃表，那么其复杂度就是log1000X，也就是一颗三层的B树就能索引到上千万行记录，另外树结构每下溯一层就需要一次磁盘IO（先不考虑buffer_pool的影响），低层高也是非常有利的。
B+树就是在B树的基础继续优化，因为B数的非叶子节点既存索引也存索引实际的行数据（非聚集索引当然没有这个问题），这样会让前面提到的16K可能就无法存储那么多索引，导致层高增加降低效率，所以B+树第一个优化就是解决这个问题：非叶子节点不存行数据。第二个优化就是叶子节点增加下一节点的指针（实际是下一页的偏移量），用于优化范围查询时的中序回溯成本。
B*树简单讲一下，就是减少了页分裂的次数。

位图

布隆过滤器