一、数据结构和算法

1、时间复杂度&空间复杂度

2、NP问题

    1）P问题：能够在多项式时间复杂度内解决的问题

    2）NP问题：能够在多项式时间复杂度内验证答案是否正确的问题

    3）NP是否等于P问题：能够在多项式时间复杂度内验证的问题，是否可以在多项式时间复杂度内解决

3、常见数据结构

    1）数组&链表

        a. 数组更适合查找多的应用，链表更适合增删多的应用

    2）hash表

        a. 既能快速访问数据，又能快速增删数据

        b. 数组与链表的结合

    3）栈

    4）队列

        a. 队列搜索好友关系中最近的有钱人

        b. 队列搜索最短路径

        -->均类似用队列进行树的层次遍历

    5）树

        a. 二叉排序树

        b. 平衡二叉树：增加节点时，需要O(1)的复杂度重新达到平衡；删除节点的时候，需要O(n)的复杂的度重新达到平衡

        c. 红黑树：平衡性不如平衡二叉树，但是解决了删除节点复杂度高的问题

    6）跳表：30分钟实现一个

4、常见算法

    1）穷举算法

    2）递归算法

        a. 快速排序算法

    3）贪心算法

        a. 背包问题求解

        b. 改进的弹性算法--迪杰斯特拉算法

    4）动态规划

二、网络通信模型

1、一次网络请求的过程



2、网络分层模型--OSI七层模型

    1）物理层

    2）数据链路层

        a. 链路层的作用：基于MAC地址进行数据传输

        b. 基于数据链路层的负载均衡：负载均衡服务器对目标服务器的MAC地址进行修改

            -> 负载均衡服务器与应用服务器集群在内网中有相同的IP地址（虚拟IP、VIP），即有相同的虚拟IP地址，但是各自的MAC地址不同

            -> 负载均衡服务器转发客户端请求时，直接修改目标MAC地址，请求的目的IP不会被改变

            -> 负载均衡服务器的压力减小，其网络带宽不会成为性能瓶颈 

    3）网络层：IP地址   

        a. 网络层的作用：根据IP地址进行目标服务器的访问

        b. 基于IP层的负载均衡：负载均衡服务器对请求的目标服务器的IP地址进行修改

            -> 负载均衡服务器和应用服务器在内网中的地址各不相同

            -> 负载均衡服务器转发客户端请求时，建立新的链接，源地址为自己，目标地址为应用服务器集群中的一台机器

            -> 应用服务器处理后，负载均衡服务器收到响应，将响应中的目标地址改为自己，源地址改为客户端，然后返给客户端

            -> 一起网络请求，涉及到一次请求转发；负载均衡服务器会成为性能瓶颈

    4）传输层：TCP/UDP 协议

        a. TCP协议：解决网络层的不可靠传输问题

        b. 3次握手

        c. 4次挥手

    5）会话层

    6）表示层

    7）应用层

        a. Http协议：请求类型、响应状态、协议版本

3、基于分层模型的网络调用

    1）调用流程：发起时自上而下，一层层的加协议头；解析时自下而上，一层层的去协议头



    2）数据包格式



4、其他

    1）TCP/IP四层模型

        a. 网络访问层

        b. 网络互联层

        c. 传输层

        d. 应用层

    2）2层负载均衡、3层负载均衡......

三、网络IO模型

1、一次网络IO的请求过程

    1）服务端启动，等待客户端发起并建立连接：socket.accept()、阻塞式等待

    2）连接建立后，服务端等待客户端的请求数据：数据读取、socket.read()、阻塞式等待

    3）服务端进行请求响应： 数据写入、socket.write()、阻塞式等待

2、多线程的IO模型

    1）一个客户端请求对应一个处理线程，每个处理线程都是new出来的

    2）一个客户端请求对应一个处理线程，处理线程是从线程池拿出来的

3、非阻塞IO模型

    1）socket通信时的IO阻塞过程

        a. accept阻塞：没有新的客户端连接时会阻塞

        b. read阻塞：从socket缓冲区读不到指定长度的数据时会阻塞

        c. write阻塞：socket缓冲区剩余长度不够时，写入数据到缓冲区会阻塞

    2）阻塞IO & 非阻塞IO

        a. 阻塞IO：进行IO操作时，用户线程会一直阻塞，知道读操作或写操作完成

        b. 非阻塞IO：进行IO操作立即返回，用户线程不会阻塞等待

    3）Java NIO：New IO、更高效、仍然是阻塞的

        a. channel类似于socket

        b. selector检查所有的channel，并且检查所有的事件：accpet事件、read可读事件、write可写事件

        c. selector是NIO的核心，它使得一个线程可以处理多个连接

        d. selectorl轮询事件的过程是阻塞的，但是这个阻塞影响不大，因为轮询事件的过程可以被任意的网络事件唤醒，如果selector被阻塞的话，表示没有任何的网络请求

        e. 读取数据的时候，是从channel对应的buffer中读取，每次读取会立即返回，不会阻塞等待，所以执行读操作后，可能并没有读到数据

4、IO复用

    1）pool & epoll

        a. poll：如果连接量大的话，每次轮询所有的socket，判断socket（channel）是否有网络事件发生的过程，会有较大的性能损耗 

        b. epoll：有网络事件发生时，除了发送事件通知，还会将触发事件的socket放在文件列中，然后每次轮询的时候，只遍历对应的事件列表，避免轮询所有的socket对象

四、数据库基本概念

1、数据库架构

    1）整体架构

        a. 连接器

        b. 语法分析器

        c. 语义分析与优化器

        d. 执行引擎

    2）为什么PreparementStatement更好

        a. 会提前生成好执行计划，当给定参数后，就可以直接执行，不用再执行语法分析、语义分析等操作

        b. 防止SQL注入攻击：因为已经生成好了执行计划，不会再进行语法分析、语义分析等操作，所以传入的参数不会再进行语法分析

2、数据库索引

    1）B-树与B+树

    2）聚簇索引：主键索引、记录和索引一起存储在叶子节点、B+树 

    3）非聚簇索引：回表

    4）合理使用索引

        a. 不盲目添加索引

        b. 删除无用的索引：索引的维护也是需要代价的，会导致增删的额外开销

        c. 使用更小的数据类型：保证B+树的一个数据块能够存储更多的索引，避免树太高

3、数据库事务

    1）事务的特性：ACID

    2）事务的实现原理：事务日志

五、其他

1、学习知识的技巧

    1）不单纯的学知识，学会推导知识，发掘知识背后的演绎过程

        a. 知识都不是凭空出现的，一定是可以被推导，可以发掘其背后的演绎过程的

        b. 学会推导知识，而不是什么都去学

    2）轻松学习知识的方法

        a. 先自己猜测，如果我做的话，我会怎么做？

        b. 寻找资料进行验证，以及纠正自己的错误

        c. 进行总结和思考：我的猜测和别人的实现有什么差别？别人为什么这么做？值得学习的地方是什么？



->学习知识，重要的是自己的思考&知识的推导过程，而不是单纯的知识学习！

->拔高自己的高度进行学习，站在更高的高度思考（系统的架构是怎样的？为什么会这样？）