序言 这次更数据结构和数据库。数据结构可能对于非科班来说不算友好，我会多介绍点学习方法；科班的同学只需要复习一遍知识，然后多刷题就行了。对于测开，数据库的掌握主要是会写sql语句，其次需要掌握《数据库系统原理》（科班必修课）里前几章内容，InnoDB底层，redis底层，具体知识点如下 数据结构 范围一般来说，面试官喜欢问十大排序里的快速排序，堆排序，冒泡排序的源码，算***涉及到数组，链表（判断是否有环、环入口、合并链表、复制复杂链表），栈（括号匹配，逆波兰式计算，实现队列），队列（实现栈），二叉树（前、中、后序遍历 递归/非递归代码；平衡二叉树，二叉排序树；B/B+树），图（问的比较少，知道深度遍历和广度遍历思想）等  学习方法（个人学习方法分享）1.科班：复习《数据结构》严蔚敏版，可以配合王道408的数据结构视频和书食用2.非科班：如果感觉上面两本书比较枯燥，可以看《大话数据结构》（听说比较有趣），配合王道视频 复习完基础知识，就需要刷《剑指offer》、Leadcode前100，边刷边总结方法。刷多了你会发现一些规律，有的题可以用刷过的方法解。刷的时候如果一开始感觉自己写比较困难，可以先参照书上的源码敲一遍，理解思路，然后逐步脱离答案，自己想解法。最后多总结，同时也要锻炼自己的调bug水平，以及工具的使用（c++ STL了解底层的话用起来很方便）   十大排序1.冒泡排序 O(n^2) * 稳定适用于基本有序、数据量小序列2.选择排序 O(n^2)3.插入排序 O(n^2)（直接插入，折半插入）4.希尔排序 O(nlogn)5.归并排序 O(nlogn)6.快速排序 O(nlogn) * 不稳定（枢轴改进方法）7.堆排序 O(nlogn) * 不稳定8.计数排序 O(n+k)9.桶排序 O(n+k)10.基数排序 O(nk)重点是上面带的排序算法源码，以及稳定性。其余算法了解即可，会源码更佳。  二叉树1.遍历前序，中序，后序遍历递归，非递归2.平衡二叉树插入自调整LL,RR,LR,RL3.红黑树 *应用：c++ set/map java HashMap（数组+链表+红黑树）当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。 五大性质：性质1. 节点是红色或黑色。性质2. 根节点是黑色。性质3.所有叶子结点都是黑色。（叶子是NIL（值为空且黑色）节点，虚拟出来的）性质4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）性质5.. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。黑色完美平衡   与平衡为二叉树对比（或问，为什么c++和java底层不用平衡二叉树）  4.B、B+树 应用：操作系统的文件索引和数据库索引 性质与区别：请自己查阅  为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引？ 图BFS、DFS找对应题刷就行了 数据库 事务1）ACID原子性、一致性、隔离性、持久性 定义2）隔离等级可串行化可重复读（mysql默认）读提交（其他大多数数据库默认）读未提交定义3）并发事务下的问题脏读不可重复读幻读定义  索引1.分类聚簇索引非聚簇索引联合索引2.InnoDB与MyISAM的区别索引方案、索引查询方式、数据存储格式、是否支持事务 范式   InnoDB技术点内存缓冲池 Buffer Pool检查点 CheckPointredo/undo页查阅资料自己理解  redis   1.持久化方法RDB/AOF2.字段基本类型 MongoDB 1.优势面向文档存储、自动分片、高度可扩展性2.存储方式虚拟内存（操作系统知识点）+持久化3.适用场景大数据  如何选择数据库   写一个sql语句推荐大家先复习完语法后刷牛客/LeadCode上的sql题，中等练完就行，要求不太高 重点增删改查多表查询   等下更，别急