线性表
数组
物理地址连续、逻辑地址连续。数组长度是固定的，不能动态增长或缩小，数组中元素的类型相同（适合用于元素个数固定，且快速用下标访问）
ArrayList（动态数组）
物理地址连续、逻辑地址连续。长度可变，可以动态增长所缩小，可以存储不同类型的元素（适合用于元素个数不确定，需要动态增删，但需要预留一定空间）
链表
物理地址不连续、逻辑地址连续。长度可变，可以动态增长所缩小，可以存储不同类型的元素（适合用于插入删除频繁，但不需要按索引快速访问，不需要预留空间）
二叉树
-
整棵树只有一个根
-
每一个节点最多有两个孩子
-
每个节点最多有一个父节点
二叉树本身的数据是毫无逻辑的
二叉搜索树
左节点小于根节点，右节点大于根节点
平衡二叉树
任意一颗子树的高度差不超过一。（维持平衡会消耗大量资源）
搜索平衡树
结合前两个的所有特点，log(n)
红黑树
特点：
-
所有的节点要么是红的，要么是黑的;·红黑树的根节点是黑色的;
-
两个红色节点不能连接在一起。两个黑色的可以。
-
所有的nil节点都是黑色的。(如果一个节点的左右节点都是空的，那这个节点就是nil节点。)
-
在一棵红黑树中根节点节点到所有的nil节点所经历的黑色节点是一致的长度。
-
综上:在红黑树中最长的分支的长度不会超过最短分支长度的二倍。
-
所有红黑树是近似平衡的二叉树。
TreeMap底层就是红黑树。
多叉树
B树（B-树）
-
B树是一种自平衡的多路查找树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
-
每个节点最多包含M-1个关键字,M是树的阶。
-
每个节点包含关键字和指向子树的指针。
-
查找、插入和删除的时间复杂度都为O(logn)。
-
适用于文件索引系统,如操作系统的文件目录,数据库索引等。
B+Tree
-
在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
-
每个非叶子节点只存储关键字信息,不存储数据,所有数据都存储在叶子节点上。
-
所有叶子节点使用链表连接,形成一个有序链表。
-
查找时先在非叶子节点上查找,再到叶子节点上查找，搜索有可能在非叶子结点结束。
-
插入和删除的时间复杂度仍为O(logn)。
-
适用于文件存储系统,数据库索引系统等。
B*Tree
-
在B+树基础上，为非叶子结点也增加链表指针。
-
在B+树基础上，将结点的最低利用率从1/2提高到2/3；
-
当一个非叶子节点满时,不直接分裂,而是将关键字转移到兄弟节点,再分裂。
-
这种方式减少了树的分裂次数,提高了空间利用率。
-
查找、插入和删除的时间复杂度仍为O(logn)。
-
适用于文件系统和数据库索引等。
