未命名

发表于 2022-06-01

1、TCP三次握手四次挥手

进行三次握手的主要作用：为了确认双方的接收能力和发送能力是否正常，指定初始化序列号是为了后面的后面的可靠传输做准备

2、TCP协议如何保证可靠传输

https://segmentfault.com/a/1190000022944999

通过下面几种机制共同保证可靠传输

（1）数据块划分

应用数据被划分为TCP认为合适发送的数据块

（2）数据排序

TCP会对每个数据进行编号，接收端对收到的数据进行排序，将有序的数据传给应用层

（3）校验和

发送端和接收端分别计算数据的数据的校验和，如果数据有差错就丢弃

（4）数据包去重

丢弃重复接收的数据

（5）超时重传

当TCP发出一个段后，会启动一个定时器，等待接收方会送确认报文，如果不能及时收到一个确认就重传

（6）流量控制

连接双方都有固定大小的缓冲区，接收端只允许发送端发送接收段缓冲区大小的数据，当接收方来不及处理发送方发送的确认数据时候，会提示发送方降低发送速率。TCP使用滑动窗口协议实现流量控制

（7）拥塞避免

慢开始
拥塞避免
快重传和快恢复

（8）ARQ协议

发送完一个分组就停止等待确认报文，收到确认报文后在发送下一个分组数据

3、从输入URL到页面加载发生了什么？

https://segmentfault.com/a/1190000006879700

4、TCP与UDP的区别

https://zhuanlan.zhihu.com/p/24860273

基于连接与无连接
对系统资源的要求
UDP程序结构相对来说简单
流模式与数据报模式
TCP可靠传输，UDP不可靠

5、计算机网络协议

（1）什么是计算机网络协议

网络协议是计算机在通信过程中要遵循的一些约定好的规则

（2）为什么对网络协议分层？

易于实现和维护，因为层与层之间是独立的，互不影响
有利于标准化的制定

（3）各层的协议与作用

应用层

通过应用进程之间的交互来完成特定的网络作用，常见的协议有：HTTP、DNS等
表示层

数据的表示、安全、压缩，确保一个系统的应用层发送的数据能被另一个系统的应用层数据读取
会话层

建立通信链路保持会话过程中链路的通畅
传输层

负责向两台主机的进程之间通信提供数据传输的服务，常见的协议有：TCP、UDP等
网络层

选择合适的网间路由与交换节点，确保数据及时送达
链路层

在物理层提供比特流传输服务的基础上，建立相邻节点之间的数据链路，通过差错控制提供数据帧（Frame）在信道上的无差错传输，常见的协议：PPP、SDLC
物理层

实现相邻计算机结点之间比特流的透明传输

6、Session、Cookie和Token的主要区别

https://blog.csdn.net/whl190412/article/details/90024671

HTTP协议是无状态的，即服务器无法判断用户身份

Cookie是保存在客户端一个小数据块，其中包含了用户信息。当客户端向服务端发起请求，服务端会像客户端浏览器发送一个Cookie，客户端会把Cookie存起来，当下次客户端再次请求服务端时，会携带上这个Cookie，服务端会通过这个Cookie来确定身份

（2）Session

Session是通过Cookie实现的，和Cookie不同的是，Session是存在服务端的。当客户端浏览器第一次访问服务器时，服务器会为浏览器创建一个sessionid，将sessionid放到Cookie中，存在客户端浏览器

（3）Token

客户端在浏览器第一次访问服务端时，服务端生成的一串字符串作为Token发给客户端浏览器，下次浏览器在访问服务端时携带token即可无需验证用户名和密码，省下来大量的资源开销

7、谈谈HTTP1.0、HTTP1.1和HTTP2.0

（1）HTTP协议的定义

HTTP协议（HyperTextTransferProtocol，超文本传输协议）是用于从WWW服务器传输超文本到本地浏览器的传输协议

（2）HTTP的基本优化

带宽
延迟

浏览器阻塞（HOL blocking）

DNS 查询（DNS Lookup）

建立连接（Initial connection）

（3）HTTP1.0 -> HTTP1.1

缓存处理
带宽优化及网络连接的使用
错误通知的管理
Host头处理
长连接

一个TCP连接上可以传送多个HTTP请求和响应

（4）HTTP 2.0 -> HTTP1.1

多路复用

单连接多资源的方式
首部压缩

静态字典、动态字典
支持服务器推送

允许服务端去完全充分地利用一个可能空闲的网络，改善页面加载时间

未命名

发表于 2022-06-01

这是我参与「第三届青训营 -后端场」笔记创作活动的的第1篇笔记

第一节课

一、什么是Go语言

高性能、高并发
语法简单、学习曲线平缓
丰富的标准库（类似与Python）
完善的工具链
静态链接
快速编译
跨平台
垃圾回收

二、Go入门

1.基础语法

（1）HelloWorld

package main

import (
	"fmt"
)

func main() {
	fmt.Println("hello world")
}
复制代码

第一行指的是main是程序的入口 import表示引入format包，这个包主要用于字符串的处理主函数main使用fmt来输出helloworld

如何编译go文件？

go run exmaple/01-hello/main.go
go build example/01-hello/main.go

变量声明

var name = value
变量名 := value

if else

if和其他语言不同，不需要有括号

循环

只有for循环，没有其他的do while循环

switch

switch后不需要加括号
分支不需要加break默认跳出

切片

可用长度的数组，一般实际情况使用切片

range

map和slice可以用range进行遍历更加方便第一个值是key 第二个值是value

指针

作用有限，主要用于修改数据

结构体

可以用结构体名称初始化变量
结构体能作为函数参数
使用指针能对结构体进行修改

错误处理

不同于Java抛出异常，Go中的错误处理可以在函数中加入error

JSON处理

可使用JSON.Marshal()进行处理
JSON.UnMarshal()反序列化

进程信息

os.Args获取进程在执行时命令行中的参数

三、Go小项目实战

Guessing Game

注意点与收获：

获取随机数需要有随机数种子seed
读取用户输入可以转化为流
项目进程中在迭代的，可以一步步完善
项目是一次性的，可以加上循环进行多次评估

SOCKET5代理服务器

注意点与收获

第一步实现TCP echo server
auth
配置请求阶段
配置relay阶段

心得体会

第一次参加字节跳动的青训营，感觉节奏很快，课后需要很多时间
老师使用的是MAC系统，proxy部分有的windows系统难以运行需要找其他的方式
go语言的清新风格与C或C++有很大的差距
课后我应该要多加练习掌握好Go的基础

未命名

发表于 2022-06-01

M1 Macbook（Monterey 12.2.1）安装Qt遇到的问题记录

一

首先执行：

1	brew install qt

没有意外报错了，错误信息如下：

Running `brew update --preinstall`...
fatal: Could not resolve HEAD to a revision
==> Auto-updated Homebrew!
Updated 1 tap (homebrew/cask).
==> New Casks
keysafe                    mixed-in-key-live          wpsoffice-cn
==> Updated Casks
Updated 40 casks.

Warning: No available formula with the name "qt".
==> Searching for similarly named formulae...
Error: No similarly named formulae found.
==> Searching for a previously deleted formula (in the last month)...
Error: No previously deleted formula found.
==> Searching taps on GitHub...
Error: No formulae found in taps.

二

那我就更新一下brew吧，执行：

1	brew update --preinstall

又是报错：

1	fatal: Could not resolve HEAD to a revision

三

应该是brew出问题了，再次用这个命令更新一下：

1	brew update --verbose

孩她妈报错：

Checking if we need to fetch /opt/homebrew...
Checking if we need to fetch /opt/homebrew/Library/Taps/homebrew/homebrew-cask...
Fetching /opt/homebrew...
Checking if we need to fetch /opt/homebrew/Library/Taps/homebrew/homebrew-core...
Fetching /opt/homebrew/Library/Taps/homebrew/homebrew-core...
Updating /opt/homebrew...
Branch 'master' set up to track remote branch 'master' from 'origin'.
Switched to and reset branch 'master'
Your branch is up to date with 'origin/master'.
Switched to and reset branch 'stable'
Current branch stable is up to date.

Updating /opt/homebrew/Library/Taps/homebrew/homebrew-core...
fatal: Could not resolve HEAD to a revision

Already up-to-date.

四

但至少信息详细了点，注意看Updating /opt/homebrew/Library/Taps/homebrew/homebrew-core...，于是我们，进入这个目录，执行下面的命令

1	cd /opt/homebrew/Library/Taps/homebrew/homebrew-core

1	git fetch --prune origin

1	git pull --rebase origin master

命令都执行完后，在更新brew就易如反掌了，最后顺利安装Qt

1	brew update

1	brew install qt

未命名

发表于 2022-06-01

未命名

发表于 2022-06-01

一、字符串排序

1、键索引计数法

2、低位优先的字符串排序

3、高位优先的字符串排序

4、三向字符串快速排序

5、字符串排序算法的选择

二、单词查找树

1、单词查找树

2、单词查找树的性质

3、三项单词查找树

4、三向单词查找树的性质

5、应该使用字符串符号表的哪种实现

三、字符串查找

1、历史简介

2、暴力字符串查找算法

3、Knuth-Morris-Pratt子字符串查找算法

4、Boyer-Moore字符串查找算法

5、Rabin-Krap指纹字符串查找算法

6、总结

四、正则表达式

1、使用正则表达式描述模式

2、缩略写法

3、正则表达式的实际应用

4、非确定有限状态自动机

5、模拟NFA的运行

6、构造与正则表达式对应的NFA

五、数据压缩

1、游戏规则

2、读写二进制数据

3、局限

4、热身运动：基因组

5、游戏编码

6、霍夫曼压缩

未命名

发表于 2022-06-01

一、无向图

1、术语表

2、表示无向图的数据类型

（1）图的几种表示方式

邻接矩阵
边的数组
邻接表数组

3、深度优先搜索

（1）走迷宫

（2）

4、寻找路径

5、广度优先搜索

6、连通分量

7、符号表

8、总结

二、有向图

1、术语

2、有向图的数据类型

3、有向图中的可达性

4、环和有向无环图

5、有向图中的强连通性

6、总结

三、最小生成树

1、原理

2、加权无向图的数据类型

3、最小生成树的API和测试用例

4、Prim算法

5、Prim算法的即时实现

6、Kruskal算法

7、展望

四、最短路径

1、最短路径的性质

2、加权有向图的数据结构

3、最短路径算法的理论基础

4、Dijkstra算法

5、无环加权有向图中的最短路径算法

6、一般加权有向图中的最短路径问题

7、展望

未命名

发表于 2022-06-01

存储器分层体系

存储管理器 -> 管理分层存储器体系

一、无存储器抽象

直接访问物理内存

在不使用存储器抽象的情况下运行多个程序

两个程序都引用了绝对的物理地址—静态重定位

二、一种存储器抽象：地址空间

将物理地址直接暴露给进程的问题：

用户程序很容易破坏操作系统
同时运行多个程序非常困难

1、地址空间的概念

解决两个问题：保护和重定位

地址空间是一个进程可用于寻址内存空间的一套地址集合，每个进程有一套自己的内存空间

地址空间的抽象概念：电话号码的前缀、IPv4地址、域名

基址寄存器和界限寄存器

动态重定位

2、交换技术

处理内存超载的两种办法：

交换

将程序完整调入内存再放回磁盘
虚拟内存

将程序的一一部分调入内存

3、空闲内存管理

跟踪内存使用情况：

位图

内存被划分为一个一个小的分配单元，对应于
空闲区链表

维护一个已分配内存段和空闲内存段的链表

三、虚拟内存

解决问题：软件膨胀

虚拟内存思想：每个程序拥有自己的地址空间，空间被分割成多块，每一块称做一页或者页面

1、分页

虚拟地址构成了虚拟地址空间，MMU负责将虚拟地址映射为物理地址

虚拟地址空间按照固定大小划分成页面

缺页中断

虚拟地址分为页号（页面的索引）和偏移量

2、页表

虚拟地址分为虚拟页号和偏移量

虚拟地址（虚拟页号 + 偏移量） -> 虚拟页号 -> 虚拟页面对应的页表项 -> 页框号 -> 页框号 + 偏移量 -> 物理地址

页表的目的：将虚拟地址转换为页框

页表项结构：访问位、修改位、保护位、“在/不在”位、页框号

虚拟内存的本质是创建了一个新的抽象概念：地址空间

虚拟内存的实现，是将虚拟地址空间分成页，并将每一个页面映射到物理内存的页框或者解除映射，

3、加速分页过程

时间和空间的问题

虚拟地址到物理地址的映射必须很快
如果虚拟地址空间很大，则页表也会很大

（1）转换检测缓冲区

转换检测缓冲区（TLB）也称相联存储器和快表

当需要查找一个虚拟地址时，先查找TLB表；如果TLB表没有就查找页表，并将该页表项替换一个TLB表项

（2）软件TLB管理

使用软件而不是硬件来处理TLB失效的问题

4、针对大内存的页表

引入TLB可以加快虚拟地址到物理地址的转换，那么如何处理巨大的虚拟地址空间呢？

（1）多级页表

引入多级页表的原因就是避免将所有的页表全都保存在内存里面

（2）倒排页表

对虚拟页面进行散列运算，建立散列表

四、页面置换算法

发生缺页中断时候，操作系统必须去选择一个页面将其换出内存

1、最优页面置换算法

2、最近未使用页面置换算法

3、先进先出页面置换算法

n、…

五、分页系统中的设计问题

六、有关的现实问题

七、分段

在机器上提供多个相互独立的称为段的地址空间

段是一个逻辑实体

未命名

发表于 2022-06-01

前言：

每个索引都对应一颗二叉树

叶子结点（用户记录） + 内节点（目录项）
聚簇索引

InnoDb会自动为主键建立聚簇索引，包含用户纪录完整信息的索引
二级索引

叶子结点由主键和索引列构成，需要进行回表操作
索引结构

每层节点按照索引值大小排成双向链表，页内记录按照索引值排列成单向链表，联合索引依次排列
索引查找记录过程

从根节点依次往下，页内：二分+遍历

一、B+树索引示例图的简化

二、索引的代价

空间
时间

三、应用B+树索引

1、扫描区间和边界条件

2、索引用于排序

3、索引用于分组

四、回表的代价

五、更好地使用索引

1、只为用于搜索、排序或分组的列创建索引

2、考虑索引列中不重复值的个数

3、索引列的值尽量小

4、为列前缀建立索引

5、覆盖索引

6、让索引列以列名的形式在搜索条件中单独出现

7、新插入纪录时主键大小对效率的影响

8、冗余和重复索引

六、总结

未命名

发表于 2022-06-01

一、不同类型的页介绍

InnoDB为了不同的目的设计了多种不同类型的页，例如：存放表空间头部的页面、存放Change Buffer信息的页、存放undo日志信息的页等等索引页（Index）

二、数据页结构快览

数据页的16KB被划分为了7个部分：

File Header
- 文件头部
Page Header
- 页面头部
Infimum + Supremum
- 页面中的最大记录和最小记录
User Records
- 用户记录
Free Space
- 空闲空间
Page Directory
- 页目录
File Trailer
- 文件尾部

三、记录在页中的存储

一开始并没有User Records，每当插入一条数据，就会在Free Space申请一个记录空间的大小，将其划分到User Records。

1、记录头的信息

delete_flag

标记当前记录是否已被删除
min_rec_flag

B+书每层非叶子节点中的最小目录项都会添加该标记
n_owned

稍后的主角
heap_no

将一条一条亲密无间排列的结构称之为堆空间（heap），从2开始
record_type

当前记录的类型：0-普通记录、1-B+树非叶子结点的目录项记录、2-Infimum记录、3-Supremum记录
next_record

从当前记录的真实数据到下一条记录真实数据的距离，记录是按照主键值从小到大排列的

四、页目录（Page Directory）

记录在页中是按照主键值由小到大的顺序串联成一个单向链表的，如果数据量非常大，查找的效率会非常低，于是引入了在页面内进行分组这种方法

过程如下：

1、将所有的正常记录（包括Infimum和Supremum记录），不包括移除到垃圾链表的记录划分为几个组

2、每个组最后一条记录中的n_owned记录属性表示该组内共有几条记录

3、每个组最后一条记录在页面中的地址偏移被单独提取出来存储，页目录中这些地址的偏移量称之为槽（Slot），每个槽占用两个字节

于是在一个数据页面中查找主键值对应的数据流程为：

1、通过二分法确定记录所在的槽（Slot），然后找到该槽所在分组中主键值最小的那一条记录

2、通过next_record属性遍历槽所在分组的各个记录

六、File Header（文件头部）

七、File Tailer（文件尾部）

八、总结

InnoDB为了不同的目的设计了不同的页，用于存放数据的页叫做数据页

一个数据页的结构如下：

File Header

页的通用信息
Page Header

数据页的专有信息
Infimum + Supremum

两个虚拟的伪记录，分别表示最大和最小记录
User Records

我们真正插入的数据
Free Space

页中尚未使用的部分
Page Directory

各个槽对应的记录在页面中地址的偏移量
File Trailer

校验页是否完整

InnoDB会将页中的记录划分为若干个组，将每个组的最后一个记录的地址偏移量作为一个槽，存放在Page Directory中

在一个页面中根据主键查找记录分为两步：

1、二分法找到槽，并找到槽所在分组中主键值最小的那条记录

2、通过记录的next_record属性遍历该槽所在的组中的各个记录

所有数据页组成一个双向链表

将页面从内存刷新到磁盘时，为了保证页面的完整性页首和页尾会存储页面的校验和

未命名

发表于 2022-06-01

所有数据页组成个双向链表，每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。

每个数据页会为里面的记录生成一个页目录，通过主键值查找记录的时候，先通过二分法定位所在的槽，在遍历槽作在的分组中的记录

一、无索引的情况

定位所在的页
在所在页内进行相关记录的查找

二、索引

1、一个简单的索引方案

2、InnoDB中的索引方案

重点！！！

（1）聚簇索引

（2）二级索引

（3）联合索引

3、InnoDB中的B+树索引的注意事项

（1）根页面万年不动窝

根节点自创建起便不会再移动

（2）内节点中目录项纪录的唯一性

（3）一个页面至少两条记录

4、MyISAM中的索引方案简介

InnoDB中索引即数据，也就是聚簇索引那棵B+树的叶子结点已经包含了所有的用户数据

5、MySQL中创建和删除索引语句

添加索引

ALTER TABLE 表名 ADD (INDEX | KEY) 索引名 (需要被索引的单个列或者多个列)
删除索引

ALTER TABLE 表名 DROP (INDEX | KEY) 索引名

三、总结

InnoDB存储引擎的索引是一棵B+树，完整的用户记录都存储在叶子节点，其他层的节点都属于内节点，内节点存储的是目录项纪录

聚簇索引：叶子结点存储所有列的值
二级索引：叶子节点存储索引值和主键值

MyISAM数据和索引分开存储

1、TCP三次握手四次挥手

2、TCP协议如何保证可靠传输

（1）数据块划分

（2）数据排序

（3）校验和

（4）数据包去重

（5）超时重传

（6）流量控制

（7）拥塞避免

（8）ARQ协议

3、从输入URL到页面加载发生了什么？

4、TCP与UDP的区别

5、计算机网络协议

（1）什么是计算机网络协议

（2）为什么对网络协议分层？

（3）各层的协议与作用

6、Session、Cookie和Token的主要区别

（1）Cookie

（2）Session

（3）Token

7、谈谈HTTP1.0、HTTP1.1和HTTP2.0

（1）HTTP协议的定义

（2）HTTP的基本优化

（3）HTTP1.0 -> HTTP1.1

（4）HTTP 2.0 -> HTTP1.1

第一节课

一、什么是Go语言

二、Go入门

1.基础语法

（1）HelloWorld

如何编译go文件？

变量声明

if else

循环

switch

切片

range

指针

结构体

错误处理

JSON处理

进程信息

三、Go小项目实战

Guessing Game

SOCKET5代理服务器

心得体会

一

二

三

四

一、字符串排序

1、键索引计数法

2、低位优先的字符串排序

3、高位优先的字符串排序

4、三向字符串快速排序

5、字符串排序算法的选择

二、单词查找树

1、单词查找树

2、单词查找树的性质

3、三项单词查找树

4、三向单词查找树的性质

5、应该使用字符串符号表的哪种实现

三、字符串查找

1、历史简介

2、暴力字符串查找算法

3、Knuth-Morris-Pratt子字符串查找算法

4、Boyer-Moore字符串查找算法

5、Rabin-Krap指纹字符串查找算法

6、总结

四、正则表达式

1、使用正则表达式描述模式

2、缩略写法

3、正则表达式的实际应用

4、非确定有限状态自动机

5、模拟NFA的运行

6、构造与正则表达式对应的NFA

五、数据压缩

1、游戏规则

2、读写二进制数据

3、局限