【回馈牛客】测开学习路线——2_数据结构和数据库

序言

这次更数据结构和数据库。
数据结构可能对于非科班来说不算友好，我会多介绍点学习方法；科班的同学只需要复习一遍知识，然后多刷题就行了。
对于测开，数据库的掌握主要是会写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,RL
  3.红黑树 *
  应用：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
    检查点 CheckPoint
    redo/undo页
    查阅资料自己理解

  • redis

  1.持久化方法
  RDB/AOF
  2.字段基本类型
  

  • MongoDB

  1.优势
  面向文档存储、自动分片、高度可扩展性
  2.存储方式
  虚拟内存（操作系统知识点）+持久化
  3.适用场景
  大数据

• 如何选择数据库
  

• 写一个sql语句
  推荐大家先复习完语法后刷牛客/LeadCode上的sql题，中等练完就行，要求不太高

  重点
  增删改查
  多表查询

等下更，别急