1. 逻辑结构
   1. 集合结构：没有联系
   2. 线性结构：一对一 头没有先驱，尾没有后继
   3. 树形结构
   4. 图形结构/网状结构
2. 物理结构
   1. 顺序存储结构：在计算机上使用一组地址连续的单元进行存储（数组）
      1. 具备随机存取的特性
      2. 插入和删除涉及移位操作，消耗性能
   2. 链式存储结构：在计算机上使用任意一组单元进行存储
      1. 失去了随机存取的特性
      2. 插入和删除效率更高，只需要改变指针域的值即可
      3. 存储密度低（包含数据域和指针域）
      4. 逻辑相邻、物理可以不相邻
      5. 链式存储可能造成内存碎片化，对内存管理不友好
   3. 数据索引存储结构：建立存储节点信息同时，还建立附加的索引表标识地址
      1. 稠密索引
      2. 稀疏索引
      3. 扩展：倒排索引
   4. 数据散列存储结构（Hash）：
      1. 基本思路：把关键码值（key）映射到表中的一个位置为访问记录，进而提高查询速度
      2. 其他：hash冲突、负载因子、初始值
3. 时间复杂度与空间复杂度
4. 常见的数据结构
   1. set
      1. 特点：无序不重复
      2. hashset：基于hashmap实现
      3. treeset：基于treemap实现
   2. 线性表
   3. 栈
      1. 先进后出 FILO
      2. 顺序栈
      3. 链栈
   4. 队列
      1. 先进先出 FIFO
      2. 顺序。。
      3. 链。。
   5. 串
      1. string
      2. stringbuilder
      3. 。。
5. 树形结构：
   1. 定义：略
   2. 二叉树
      1. 二叉排序树
         1. 一定左小右大
         2. 查找、插入时间复杂度为O(lnN)
      2. 平衡二叉树(avl)
         1. 特点;所有节点的左右子树高度差不超过1
      3. 红黑树(rbtree)
         1. 本质也是平衡二叉树
         2. 特征
            1. （1）每个结点要么是红的要么是黑的
            2. （2）根节点只能是黑色
            3. （3）叶子节点必须是黑色（叶子是NIL节点）
            4. （4）如果一个节点是红色的，那么它的父节点是黑色，它的两个儿子节点是黑色的
               1. ① 从每个叶子到根的所有路径上不能有两个连续的红色节
               2. ② 从根节点到叶子节点的所有路径上不能出现2个连续的红色节点
            5. （5）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
         3. 其他：红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多——实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
      4. 哈夫曼树 （最优二叉树）：带权二叉树 略
   3. 多叉树：（掌握）
      1. 出现原因：每个节点存储的元素数量有限，如果元素数量过多，就会退化为原始的线性链表查询
      2. b-树
         1. 特点
            1. 每个节点可以存储超过2 个元素 ，可以有超过2的子节点
            2. 拥有AVL平衡树的特点 任何节点子树深度不超过1
            3. 拥有二叉搜索树的特点 左小右大
            4. B树比较矮，分叉越多，树越矮，IO次数越少，搜索性能越高
            5. 三阶B树最多有3个分叉 ，四阶B树最多拥有4个分叉
            6. M阶的B树每个节点最多存储M-1个元素，最多拥有M个子节点 叶子节点只存储数据
      3. b+树
         1. 基于B树的变种，多用于数据库和文件系统
         2. 特点
            1. 分为内部节点(非叶子节点)和叶子节点2种
            2. 内部节点只存储KEY，不存储具体数据
            3. 叶子节点存储KEY和具体数据
            4. 所有的叶子节点形成一个有序链表
            5. B树的节点存储的元素个数是M，那么它的子节点数量是M+1个，而B+树的节点元素个数和子节点数是一样的
      4. B+树相对于B树的优势
         1. 每个节点存储更多的KEY，树的高度更低，时间复杂度越小，查询越快
         2. 数据在叶子节点，每次查询都要查询到叶子节点，查询速度比较稳定
         3. 叶子节点构成构成了链表结构，方便区间查询和排序
      5. Mysql为什么使用B+树：
         1. 以最小的IO找到更多的记录数，如果是B树，由于每个节点要存储Key和Value(数据) ，那么每个节点能存储的Key是很少的 ，而B+树每个节点只存储Key，它可以存储更多的Key, 每个节点存储的Key越多，路数越多，节点就越少，需要耗时的IO就越少，查找性能就越高 ， 且B+树的叶子节点是有序的，形成链表，方便区间查询和排序
   4. 图：略
6. 常见算法 ：
   1. 散列算法
      1. Hash算法是把任意长度输入变为固定长度输出，不同的输入可能散列成相同的Hash值（Hash冲突）
      2. 哈希冲突的4种解决方法：
         1. 拉链法/链地址法
         2. 开放寻址法
         3. 再散列法
         4. 建立公共溢出区
   2. 递归
      1. 注意：需要有出口 ——栈溢出
   3. 排序算法
      1. java中的排序
         1. 常见方法
            1. Arrays.sort ：元素少于 47 ，使用插入排序 ，元素少于286使用快速排序
            2. Collections.sort
         2. 实现comparable接口
         3. 传入比较器Comparator
      2. 
         —
   4. 查找算法
      1. 顺序查找 ：无序数据查找,从前往后查找
      2. 二分查找