算法与数据结构

BTree和B+tree

• BTree
  B树是为了磁盘或者其他存储设备而设计的一种多叉平衡查找树，相对于二叉树，B树的每个内节点有多个分支，即多叉。

  参考文章：https://www.jianshu.com/p/da5...

• B+Tree
  B+树是B树的变体，也是一种多路搜索树。

  参考文章：https://www.jianshu.com/p/da5...

排序算法

• 快速排序
  快速排序是十分常用的高效率的算法，其思想是：先选一个标尺，用它把整个队列过一遍筛选，以保证其左边的元素都不大于它，其右边的元素都不小与它

  function quickSort($arr){
  
    // 获取数组长度
    $length = count($arr);
  
    // 判断长度是否需要继续二分比较
    if($length <= 1){
      return $arr;
    }
  
    // 定义基准元素
    $base = $arr[0];
  
    // 定义两个空数组，用于存放和基准元素的比较后的结果
    $left = [];
    $right = [];
  
    // 遍历数组
    for ($i=1; $i < $length; $i++) { 
  
      // 和基准元素作比较
      if ($arr[$i] > $base) {
        $right[] = $arr[$i];
      }else {
        $left[] = $arr[$i];
      }
  
    }
  
    // 然后递归分别处理left和right
    $left = quickSort($left);
    $right = quickSort($right);
  
    // 合并
    return array_merge($left,[$base],$right);
    
  }

• 冒泡排序
  思路：法如其名，就像冒泡一样，每次从数组中冒出一个最大的数
  比如：2，4，1 
  第一次冒出4：2，1，4
  第二次冒出2：1，2，4

  function bubbleSort($arr){
  
    // 获取数组长度
    $length = count($arr);
  
    // 第一层循环控制冒泡轮次
    for ($i=0; $i < $length-1; $i++) { 
      
      // 内层循环控制从第0个键值和后一个键值比较，每次冒出一个最大的数
      for ($k=0; $k < $length-$i-1; $k++) { 
        if($arr[$k] > $arr[$k+1]){
          $tmp = $arr[$k+1];
          $arr[$k+1] = $arr[$k];
          $arr[$k] = $tmp;
        }
      }
    }
  
    return $arr;
  }

• 选择排序
  思路：每次选择一个相应的元素，然后将其放到指定的位置

      function selectSort($arr){
       
        // 实现思路
        // 双重循环完成，外层控制轮数，当前的最小值，内层控制比较次数
  
        // 获取长度
        $length = count($arr);
    
        for ($i=0; $i < $length - 1; $i++) { 
          // 假设最小值的位置
          $p = $i;
    
          // 使用假设的最小值和其他值比较，找到当前的最小值
          for ($j=$i+1; $j < $length; $j++) { 
            // $arr[$p] 是已知的当前最小值
    
            // 判断当前循环值和已知最小值的比较，当发下更小的值时记录下键，并进行下一次比较
            if ($arr[$p] > $arr[$j]) {
              $p = $j; // 比假设的值更小
            }
          }
    
          // 通过内部for循环找到了当前最小值的key,并保存在$p中
          // 判断 日光当前$p 中的键和假设的最小值的键不一致增将其互换
          if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
          }
        }
        // 返回最终结果
        return $arr;
      }

计算机网络

TCP/UDP区别

• TCP 
  TCP是一种面向连接的、可靠的、基于字节流的传输层通信协议
  TCP面向连接，提供可靠地数据服务
  TCP首部开销20字节
  TCP逻辑通信信道是全双工的可靠信道
  TCP连接只能是点到点的
• UDP
  UDP是参考模型中一种无连接的传输层协议，提供面向事务的简单不可靠的信息传递服务
  UDP无连接，不可靠
  UDP首部开销8字节
  UDP逻辑通信信道是不可靠信道
  UDP没有拥塞机制，因此网络出现拥堵不会使源主机的发送效率降低
  UDP支持一对一，多对一，多对多的交互通信

三次握手，四次挥手，为什么是三次握手四次挥手

在TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握手建立一个连接，完成三次握手,客户端与服务器开始传送数据。
简单点说：A与B建立TCP连接时，首先A向B发送SYN（同步请求），然后B回复SYN+ACK（同步请求应答），最后A回复ACK确认，这样TCP的一次连接（三次握手）就完成了。

• TCP三次握手

  所谓三次握手，是指简历一个TCP连接时需要客户端和服务器总共发送三个包
  三次握手的目的是连接服务器指定端口，简历TCP连接，并同步连接双方的序列号并交换TCP窗口大小信息。
  TCP三次握手图解：
  

  1. 第一次握手
     客户端发送一个TCP的SYN标志位置1的包，指明客户打算连接的服务器的端口，以及初始化序号，保存在包头的序列号字段里
  2. 第二次握手
     服务器发挥确认包应答，即SYN标志位和ACK标志均为1，同时将确认序号设置为客户的ISN加1，即X+1
  3. 第三次握手
     客户端再次发送确认包，SYN标识为0，ACK标识为1，并且把服务器发来的序号字段+1，放在确定字段中发送给对方，并且在数据字段写入ISN的+1

简单解释TCP三次握手：
参考：https://github.com/jawil/blog...

• 四次挥手

  TCP的连接的拆除需要发送四个包，因此称为四次挥手。客户端或服务器均可主动发起挥手动作。
  由于TCP连接时全双工的，因此每个方向都必须单独进行关闭。这个原则是当一方完成他的数据发送任务后就能发送一个FIN来终止这个方向的连接。收到一个FIN只意味着这一方向上没有数据流动，一个TCP连接在收到一个FIN后仍能发送数据。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。

• 为什么是三次握手四次挥手
  这是因为服务端的LISTEN状态下的socket当收到SKY报文的简历连接的请求后，它可以把ACK和SYN放在一个报文里来发送。但关闭连接时，当收到对方的FIN报文通知时，他仅仅表示对方没有数据发送给你了，但未必你的所有数据都全部发送给对方了，所以你可以不是马上回关闭socket，即你可能还会发送一些数据给对方之后，在发送FIN报文给对方来表示你同意现在可以关闭连接了，所以这里的ACK和FIN报文多情况下都是分开发送的。

长连接和短连接

TCP在真正的读写操作之前，server和client之间必须建立一个连接，当读写操作完成后，双方不再需要这个链接时他们可能释放这个连接，连接的建立是通过三次握手，释放则需要四次挥手，所以说每个连接的建立都是需要消耗资源和时间的。

• TCP短连接

  1. client向server发起连接请求
  2. server接到请求，双方建立连接
  3. client向server发消息
  4. server回应client
  5. 一次读写完成，此时双方任何一个都可以发起close操作
     一般都是client先发起close操作，因为一般的server不会回复完client就立即关闭连接

所以短连接一般只会在client和server间传递一次读写操作，短连接管理起来比较简单，存在的连接都是有用的连接，不需要额外的控制手段

• 长连接

  1. client向server发起连接
  2. server接到请求后，双方建立连接
  3. client向server发送消息
  4. server回应client
  5. 一次读写完成，连接不关闭
  6. 后续读写操作

• 长/短连接的操作过程

  1. 短连接的操作步骤：
     建立连接 -> 数据传输 -> 关闭连接
  2. 长连接的操作步骤：
     建立连接 -> 数据传输 -> （保持连接） -> 数据传输 -> 关闭连接

• 长/短连接的优缺点

  1. 长连接可以省去较多的TCP建立和关闭操作，减少资源浪费，节省时间，对于比较频繁的请求资源的客户端比较适用于长连接
  2. 短连接对于服务器来说管理较为简单，存在的连接都是有用的连接，不需要额外的控制手段

从浏览器输入域名到展示页面都发生了什么

• DNS域名解析
  先找本地hosts文件，检查对应域名ip的关系，有则想ip地址发送请求，没有再去找DNS服务器
• 建立TCP连接
  拿到服务器IP后，向服务器发送求求，三次握手，建立TCP连接
  
• 
  简单理解三次握手：
  客户端：您好，在家不，有你快递
  服务端：在的，送来吧
  客户端：好滴，来了
• 
  
• 发送HTTP请求
  与服务器建立连接后，就可以向服务器发起请求了。具体请求内容可以在浏览器中查看
• 服务器处理请求
  服务器收到请求后由web服务器（Apache，Nginx）处理请求,web服务器解析用户请求，知道了需要调用那些资源文件，再通过相应的这些资源文件处理用户请求和参数，并调用数据库等，然后将结果通过web服务器返回给浏览器
• 返回响应结果
  在响应结果中都会有一个HTTP状态码，诸如我们熟知的200、404、500等
  状态码都是由三位数字和原因短语组成，大致为五类：
  1XX 信息性状态码 接收的请求正在处理
  2XX 成功状态码 请求正常处理完毕
  3XX 重定向状态码 需要附加操作以完成请求
  4XX 客户端错误状态码 服务器也无法处理的请求
  5XX 服务器错误状态码 服务器请求处理出错
• 关闭TCP连接
  为了避免服务器与客户端双方资源占用和消耗，当双方没有请求或者响应传递时，任意一方都可以发起关闭请求，与创建TCP连接的三次握手类似，关闭TCP连接需要4次挥手
  简单比喻为：
  客户端：哥们，我这边没有数据要传了，咱们关闭连接吧
  服务端：好的，我看看我这边还有数据不
  服务端：兄弟，我这边也没数据要传给你了，咱们可以关闭连接了
  客户端：好嘞
• 浏览器解析HTML
• 浏览器布局渲染