《微观经济学》读书笔记
数据结构系列（四）图、网结构总结
逻辑结构
图的种类
维基百科对图（Graph）的定义：
A graph is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically.
无向图（Undirected Graph）
任何两个顶点（vertex）之间都有边（edge）的无向图称为无向完全图。一个具有 n 个顶点的无向完全图的边数为：
$$
C^2_n=n(n-1)/2
$$
有向图（Directed Graph）
任何两个顶点（vertex）之间都有弧（arc）的有向图称为有向完全图。一个具有 n 个顶点的有向完全图的弧数为：
$$
P^2_n=n(n-1)
$$
带权图（Weighted Graph）
边或弧上带有权值的图，也称为网（network）。
维基百科对网（network）的定义：
In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes (e.g. names).
图（graph）是高度抽象后的逻辑结构，而网（network）在此之上可以通过在顶点（vertex）和边（edge）上增加属性来包含更多的信息，更偏重于对实际问题的建模。
图的相关术语
https://en.wikipedia.org/wiki/Glossary_of_graph_theory
What’s the difference between Adjacency and Connectivity ?
在无向图中，邻接是点与点或者边与边之间的关系。在无向图中，如果两个点之间至少有一条边相连，则称这两个点是邻接的。同样，如果两条边有共同的顶点，则两条边也是邻接的。关联是点与边之自的关系。一个点如果是一条边的顶点之一，则称为点与该边关联。
- https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
- https://en.wikipedia.org/wiki/Glossary_of_graph_theory#adjacent
存储结构
邻接矩阵（Adjacency Matrix）
维基百科对矩阵（Matrix）的定义：
In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.
维基百科对矩阵（Matrix）的定义 2：
数学上，一个 $m×n$ 的矩阵是一个由 $m$ 行（row）$n$ 列（column）元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。
矩阵（Matrix）是很多科学计算问题研究的对象，矩阵可以用二维数组来表示。
图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
定义如下：
设 $G=(V,\ E)$ 是一个图，其中 $V={v_0,\ v_1,\ …\ ,\ v_{n-1}}$，那么 $G$ 的邻接矩阵 $A$ 定义为如下的 $n$ 阶方阵：
$$
A_{[i][j]}=
\begin{cases}
1& {若\ (v_i,\ v_j)\ 或\ <v_i,\ v_j>\ ∈\ E}\
0& {若\ (v_i,\ v_j)\ 或\ <v_i,\ v_j>\ ∉\ E}
\end{cases}
$$
可见，若无向图 $G$ 中有 $n$ 个顶点 $m$ 条边，采用邻接矩阵存储，则该矩阵中非 0 元素的个数为：
$$
2m
$$
对称矩阵（Symmetric Matrix）
用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。为什么这么说呢？
对于无向图来说，如果 $A_{[i][j]}$ 等于 1，那 $A_{[j][i]}$ 也肯定等于 1。实际上，我们只需要存储一个就可以了。也就是说，无向图的二维数组中，如果我们将其用对角线划分为上下两部分，那我们只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了。
上面描述的是一类特殊矩阵：
若一个 $n$ 阶方阵 $A$ 中的元素满足下述条件：
$$
a_{ij}=a_{ji} \quad (0≤i,\ j≤n-1)
$$
则 $A$ 称为对称矩阵（Symmetric Matrix）。
In the mathematical discipline of linear algebra, a symmetric matrix is a square matrix that is equal to its transpose.
对称矩阵可以压缩存储：对称矩阵有近一半的元素可以通过其对称元素获得，为每一对对称元素只分配一个存储单元，则可将 $n^2$ 个元素压缩存储到含有 $n(n＋1)/2$ 个元素的一维数组中。
三角矩阵（Triangular Matrix）
以对称矩阵的主对角线为界，上（下）半部分是一个固定的值（如 0），这样的矩阵称为：上三角矩阵（Upper Triangular Matrix）或下三角矩阵（Lower Triangular Matrix）。
In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix. A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero.
稀疏矩阵（Sparse Matrix）
如果我们存储的是稀疏矩阵（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。
这里描述的是一类「非零元素个数很少的矩阵」，即稀疏矩阵（Sparse Matrix）。
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero.
稀疏矩阵可以压缩存储，使用三元组表示法：$(i,\ j,\ a_{ij})$。
总结，邻接矩阵的存储方法的优点：
- 首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。
- 其次，用邻接矩阵存储图的另外一个好处是方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。比如求解最短路径问题时会提到一个 Floyd-Warshall 算法，就是利用矩阵循环相乘若干次得到结果。参考：《矩阵运算及其运算规则》
此外，针对邻接矩阵比较浪费存储空间的缺点，解决方案：
- 不带权的无向图的邻接矩阵，一定是一个对称矩阵，因此可以转为三角矩阵之后进行压缩存储。
- 有向图、带权图的邻接矩阵，一般都不是一个对称矩阵。但如果是一个稀疏矩阵，可以使用三元组表示法进行压缩存储。
邻接表（Adjacency List）
邻接表（Adjacency List） 的定义：
In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.
还记得我们之前讲过的时间、空间复杂度互换的设计思想吗？邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。
就像图中的例子，如果我们要确定，是否存在一条从顶点 2 到顶点 4 的边，那我们就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。而且，我们前面也讲过，链表的存储方式对缓存不友好。所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。
在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。所以，我们也可以将邻接表同散列表一样进行 “改进升级”。
我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选择用红黑树。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。当然，这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。除此之外，我们还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。
图的应用
图的搜索（遍历）
https://en.wikipedia.org/wiki/Graph_traversal
图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。具体方法有很多，比如两种最简单、最 “暴力” 的深度优先、广度优先搜索，还有 A*、IDA* 等启发式搜索算法。
连通图的两种搜索方式：
| 邻接矩阵 | 邻接表 | |
|---|---|---|
| 深度优先搜索 | 栈（LIFO）实现（$O(n+e)$） | |
| 广度优先搜索 | 队列（FIFO）实现 |
深度优先搜索（DFS）
https://en.wikipedia.org/wiki/Depth-first_search
深度优先搜索（Depth-first search, DFS）类似于树的先序遍历。
想象成“走迷宫”的过程。
实际上，深度优先搜索用的是一种比较著名的算法思想——回溯思想。这种思想解决问题的过程，非常适合用递归来实现。而递归的本质就是压栈与出栈操作。
深度优先搜索的栈（LIFO）实现，过程如下图，将压栈 push 的顶点序列输出即可。
广度优先搜索（BFS）
https://en.wikipedia.org/wiki/Breadth-first_search
广度优先搜索（Breadth-first search, BFS）类似于树的层次遍历。
想象成 “地毯式搜索” 层层推进的过程。
广度优先搜索的队列（FIFO）实现，过程如下：
首先顶点入队，并输出。
然后顶点出队。
将出队顶点相连的所有顶点依次入队，并输出。
重复 2、3 两步，直到所有顶点输出为止，最终结果不唯一。
连通分量
无向图中的极大连通子图（Maximal connected subgraph）称为原图的连通分量（Connected Components）。
连通图只有一个极大连通子图，就是它本身。
最小生成树问题（MST problem）
如果无向图中，任意两个顶点都连通，称为连通图（Connected Graph）。如下图：
如果连通图中，边上有权值，称为连通网（Connected Network）。如下图：
连通图的一次遍历所经过的点和边的集合，构成一棵生成树（Spanning Tree）。
一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图（Minimum connected subgraph）。
一个具有 $n$ 个顶点的连通图，它的生成树的边数为 $n-1$。
连通图的遍历序列不是唯一的，所以能得到不同的生成树。其中权值总和最小的生成树，称为最小生成树（Minimum Spanning Tree, MST）。如下图：
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.
最小生成树的准则：
- 必须使用且仅使用连通网中的
n-1条边来联结网络中的n个顶点； - 不能使用产生回路的边；
- 各边上的权值总和达到最小。
最小生成树的应用：规划出总长度最小的网络
- 例如工程领域设计，如最小成本的铺设网线、电缆、管道、道路、…
- https://en.wikipedia.org/wiki/Minimum_spanning_tree#Applications
Prim 算法
https://en.wikipedia.org/wiki/Prim%27s_algorithm
假设 $N=(V,\ E)$ 是连通网，$TE$ 是 $N$ 上最小生成树中边的集合：
初始态：$U={u_0},\ (u_0∈V),\ TE={}$
在所有 $u∈U,\ v∈V-U$ 的边 $(u,\ v)∈E$ 中找一条代价最小的边 $(u,\ v_0)$ 并入集合 $TE$，
同时 $v_0$ 并入 $U$重复 2，直到 $U=V$
形象化理解：由点找边再找点的过程。
📝 习题 📝
Kruskal 算法（加边法）
https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
假设 $N=(V,\ E)$ 是连通网
- 非连通图 $T={V,\ {}}$，图中每个顶点自成一个连通分量
- 在 $E$ 中找一条代价最小，且其两个顶点分别依附不同的连通分量的边（即不形成回路的边），将其
加入 $T$ 中 - 重复 2，直到 $T$ 中所有顶点都在同一连通分量上
形象化理解：由边找点。
最短路径问题（Shortest path problem）
在图论中，最短路径问题是在连通图中寻找两个顶点之间的一条路径，使得其组成边的权重（如时间、距离、费用等）之和最小化的问题。
最短路径的应用：
- 例如规划交通路线、解决运输问题、编制生产计划、…
- https://en.wikipedia.org/wiki/Shortest_path_problem#Applications
最短路径的计算方法：
最短路径算法还有很多，比如 Bellford 算法、Floyd 算法等等。
回溯算法
从终点开始，逐步逆向推算。（从终点到起点的逆向回溯过程。）
Dijkstra 算法
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
《44 | 最短路径：地图软件是如何计算出最优出行路径的？》
📝 习题 📝
| 目的地 | 起点：甲 | 前驱 | 最短路径 |
|---|---|---|---|
| 1 ✅（2️⃣） | 33 | 甲 | 甲 - 1 |
| 2 ✅（1️⃣） | 27 | 甲 | 甲 - 2 |
| 3 ✅（4️⃣） | 52 | 甲 | 甲 - 3 |
| 4 ✅（3️⃣） | 47 | 2 | 甲 - 2 - 4 |
| 5 ✅（6️⃣） | 甲 - 2 - 4 - 乙 - 5 | ||
| 乙 ✅（5️⃣） | 甲 - 2 - 4 - 乙 |
A* 算法
https://en.wikipedia.org/wiki/A*_search_algorithm
《49 | 搜索：如何用 A * 搜索算法实现游戏中的寻路功能？》
最大流问题（Maximum flow problem）
https://en.wikipedia.org/wiki/Maximum_flow_problem
当以物体、能量或信息等作为流量流过网络时，怎样使流过网络的流量最大，或者使流过网络的流量的费用或时间最小。通常，把设计这样的流量模型问题，叫作网络的流量问题。
最大流量问题，就是在一定条件下，要求流过网络的流量为最大的问题。
📝 习题 📝
拓扑排序（Topological sorting）
拓扑排序算法：
- 在有向图中选一个入度为 0 的顶点并输出。
- 从图中删除该顶点和所有以它为尾的弧。
重复 1、2 两步，直到所有顶点输出为止，最终结果不唯一。
设某有向图中有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为 $O(n+e)$。
https://en.wikipedia.org/wiki/Topological_sorting
社交网络（Social network）
图的两种存储结构，在社交应用的优缺点对比如下。例如在微博（有向图）中，设我为 $v_i$，ta 为 $v_j$：
- 邻接矩阵
- 优点：
- 存储方式简单、直接，因为基于数组，用户之间的关系获取（$O(n)$）、建立（$O(1)$）、查找（$O(1)$）非常高效。
- 缺点：
- 比较浪费存储空间。
- 获取的好友关系无序。
- 优点：
- 邻接表：
- 优点：
- 节约存储空间。
- 获取的好友关系可以按关键字排序。
- 缺点：
- 用户之间的关系建立、查找相对低效（取决于”关系“使用的数据结构）。
- 关注列表（邻接表）、粉丝列表（逆邻接表）需要分别存储、同时维护，关系维护相对繁琐。
- 优点：
| 需求 | 邻接矩阵 | 邻接表 A、逆邻接表 R |
|---|---|---|
| 我关注的人 | $A_{[i][0-n]}$ | $A_{[i]}$ |
| 我的粉丝（关注我的人） | $A_{[0-n][i]}$ | $R_{[i]}$ |
| 我关注 ta | $A_{[i][j]}$ = 1 | insert($A_{[i]}$, $v_j$) && insert($R_{[j]}$, $v_i$) |
| 我取消关注 ta | $A_{[i][j]}$ = 0 | delete($A_{[i]}$, $v_j$) && delete($R_{[j]}$, $v_i$) |
| 我是否关注 ta | $A_{[i][j]}$ == 1 | exist($A_{[i]}$, $v_j$) |
| ta 的粉丝是否有我 | $A_{[i][j]}$ == 1 | exist($R_{[j]}$, $v_i$) |
基于上述存储结构，可以进一步实现如下需求（以邻接表为例）：
1 | # 求共同关注 |
知识图谱（Knowledge graph）
https://en.wikipedia.org/wiki/Knowledge_graph
参考
https://en.wikipedia.org/wiki/Graph_theory
https://en.wikipedia.org/wiki/Network_theory
数据结构系列（三）树结构总结
相关术语
维基百科 Tree (data structure) 的相关术语：
结点（Node）：包含一个数据元素及若干指向其子树的分支。
结点的度（Degree of node）：
For a given node, its number of children. A leaf has necessarily degree zero.
树的度（Degree of tree）：
The degree of a tree is the maximum degree of a node in the tree.
高度（Height）、深度（Depth）：
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.
The depth of a node is the length of the path to its root (i.e., its root path).
When using zero-based counting, the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
参考：
https://www.baeldung.com/cs/tree-depth-height-difference
https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height
一叉树
有没有想过为啥有二叉树，而没有一叉树？实际上顺序表、链式表就是特殊的树，即一叉树实现。
二叉树
二叉树的五种基本形态：
注意：一棵树（包括二叉树）的最少结点个数为 0（空树）。
二叉树的常见形态：
- 二叉树
- 满二叉树
- 完全二叉树
二叉树的通用性质：
性质 1：二叉树第 i (i ≥ 1) 层至多有 $2^{i-1}$ 个结点。
性质 2：深度为 k (k ≥ 1) 的二叉树至多有 $2^k-1$ 个结点。
性质 3：二叉树中，若度数为 0 的叶子结点个数为 $n_0$，度数为 2 的结点个数为 $n_2$，则 $n_0 = n_2 + 1$。
若根节点的层数为 1，则具有 n 个结点的二叉树的最大高度为 n（即一叉树）。
参考：https://www.atnyla.com/tutorial/level-and-height-of-the-tree/3/392
逻辑结构
下面介绍几种特殊的二叉树：
满二叉树（Full Binary Tree）
满二叉树的性质：
深度为 k (k ≥ 1) 的满二叉树，共有 $2^k-1$ 个结点。如下图和表格：
$k=1$ $k=2$ $k=3$ $k=4$ 结点总数 $2^1-1=1$ $2^2-1=3$ $2^3-1=7$ $2^4-1=15$
完全二叉树（Complete Binary Tree）
完全二叉树的性质：
含有 n 个结点的完全二叉树，深度为 $⌊log_2n⌋+1$。
深度为 k 的完全二叉树：
$k=1$ $k ≥ 2$ 最少结点数 $2^{k-1}$ $2^{k-1}$ 最少叶子结点数 $k$ $2^{k-2}$ 如下图和表格：
$k=1$ $k=2$ $k=3$ $k=4$ 最少结点数 $2^{1-1}=1$ $2^{2-1}=2$ $2^{3-1}=4$ $2^{4-1}=8$ 最少叶子结点树 1 $2^{2-2}=1$ $2^{3-2}=2$ $2^{4-2}=4$ 含有 n 个结点的完全二叉树按层编号，则：
存储结构
顺序存储结构
如果将完全二叉树按层编号，并以编号作为数组下标将结点存入一维数组中，则完全二叉树的顺序存储结构如下图：
通过观察，完全二叉树按层编号之后，编号之间的关系满足下图的编号计算公式。
公式可以准确反映出结点之间的逻辑关系，可用于求某结点的父、子结点。（这一性质是二叉树顺序存储结构的基础）
但如果将非完全二叉树按层编号进行顺序存储，则无法套用编号计算公式求父、子结点：
| 优点 | 缺点 | |
|---|---|---|
| 方式一：直接对结点按层编号，然后再将各结点按编号存入数组。 | 节省存储空间。 | 无法根据结点间的下标关系确定它们之间的逻辑关系，从而难以实现二叉树求父、子结点等基本运算。 |
| 方式二：先增设虚拟节点，将其转为一棵完全二叉树，然后再按层编号存入数组。 | 方便实现二叉树求父、子结点等基本运算。 | 浪费存储空间。 |
所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
当我们讲到堆和堆排序的时候，你会发现，堆其实就是一种完全二叉树，最常用的存储方式就是数组。
链式存储结构
二叉树有不同的链式存储结构，其中最常用的是二叉链表和三叉链表，其结点形式如下图：
二叉树的两种链式存储结构如下图：
其中，判断叶子结点的条件为：(p->lchild == NULL) && (p->rchild == NULL)。
基本运算
树常见的基本运算如下：
- 初始化（Init）
- 建树（Create）
- 插入、删除结点
- 求根（Root）
- 求双亲（Parent）
- 求孩子（Child）
- 二叉树求左孩子（Lchild）
- 二叉树求右孩子（Rchild）
- 遍历（Traverse）
- 二叉树先序遍历（PreOrderTraverse）
- 二叉树中序遍历（InOrderTraverse）
- 二叉树后序遍历（PostOrderTraverse）
- 层次遍历（LevelOrder）：从上往下逐层遍历，同一层中结点从左往右
遍历
https://en.wikipedia.org/wiki/Tree_traversal
已知二叉树，求遍历序列
二叉树的遍历（traversing binary tree），是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问有且仅被访问一次。
二叉树的遍历，有三种经典方式：
| 经典的三种遍历方式 | 遍历顺序 | 推导 |
|---|---|---|
| 先序遍历 | DLR | 首先访问父节点，因此先序序列的第一个结点必为根节点 （如下图先序遍历 A） |
| 中序遍历 | LDR | 先于根结点的为左子树，后于根结点的为右子树 |
| 后序遍历 | LRD | 最后访问父节点，因此后序序列的最后一个结点必为根节点 （如下图后序遍历 A） |
已知二叉树，求三种遍历序列：
归纳：
- 若一棵非空二叉树的先序序列和后序序列相同，则该二叉树中只有一个根节点。
- 若一棵具有 n (n>0) 个结点的二叉树的先序序列和后序序列正好相反，则该二叉树一定是：高度为 n 的二叉树。
- 若一棵二叉树的先序序列和中序序列正好相反，则二叉树上每个结点的右子树都是空二叉树。
已知遍历序列，求二叉树
由二叉树的遍历可知，任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。已知先序或后序序列 + 中序序列，可以确定一棵二叉树：
问题：
- 假设一棵二叉树的中序序列与后序序列分别为：
BACDEFGH和BCAEDGHF，建立该二叉树。
分析：
二叉树遍历的实现方式
- 递归实现
- 非递归实现（栈）
多叉树
B-tree
B-tree 的阶（Order），来自 Knuth (1998) 的定义：
Knuth (1998) defining the order to be maximum number of children (which is one more than the maximum number of keys).
所以按照 Knuth 定义一棵 m 阶的 B 树（国内教材所用的定义）：
Every node has at most m children.
每个节点最多有 m 个孩子。
Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.
非叶非根节点至少有 [m/2] 个儿子。[m/2] 表示取大于 m/2 的最小整数。
The root has at least two children if it is not a leaf node.
根节点至少有 2 个儿子。除非它本身是叶子节点，即整棵树只有它一个节点。
A non-leaf node with k children contains k − 1 keys.
非叶节点：有 k 个儿子，就有 k-1 个 keys。
All leaves appear in the same level and carry no information.
所有叶子节点在同一层，不携带信息 data。
例如一棵 3 阶 B 树，高度相比二叉树会更低。
B+ Tree
特性：
- 非叶子节点存储索引；
- 叶子节点存储数据，且通过双向链表关联。
为什么用？
为了减少内存开销和磁盘 IO
B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就可以存储更多的键值，相应的树的阶数就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数会再次减少，数据查询的效率也会更快。另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。
为了支持区间查找
因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，叶子节点间通过双向链表连接。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。
树和森林
https://en.wikipedia.org/wiki/Tree_structure
逻辑结构
无回路的连通图（Connected Graph）即为树。
存储结构
森林（Forest）：n 棵互不相交的树的集合。
A set of n ≥ 0 disjoint trees.
https://blog.csdn.net/chengyq116/article/details/112342319
https://slidetodoc.com/left-childright-sibling-representation-instructor-prof-jyhshing-roger/
树的应用
分类算法
哈夫曼树（最优二叉树）
https://en.wikipedia.org/wiki/Huffman_tree
哈夫曼树的性质：
- 哈夫曼树中，不存在度数为 1 的分支结点。
- 若度数为 0 的叶子结点个数为 $n_0$，则哈夫曼树共有 $2n_0 - 1$ 个结点。
- 若度数为 2 的结点个数为 $n_2$，则哈夫曼树共有 $2(n_2 + 1) - 1$ 个结点。
【霍夫曼编码原理 文本压缩、ZIP压缩文件原理 Huffman Encoding by Tom Scott-哔哩哔哩】 https://b23.tv/wFatkFc
【Huffman 编码动画演示】 https://www.bilibili.com/video/BV18V411v7px/
查找
二叉查找树（Binary Search Tree, BST）
中序遍历时从小到大的二叉树。
平衡二叉查找树（Balanced Binary Search Tree, BBST）
排序
堆排序（Heap）
《29 | 堆的应用：如何快速获取到 Top 10 最热门的搜索关键词？》
参考
-
B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.[2]Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as disks. It is commonly used in databases and file systems.
B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,[1] typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
2–3 tree is a B–tree of order 3.
2–3–4 tree is a B–tree of order 4.
R-tree，R 树是 B 树向多维空间发展的另一种形式
《23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？》
《24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？》
数据结构系列（二）线性结构总结
数组
线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻按关系决定它们在存储空间中的存储位置，即：逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。因此，数组可以看成线性表的一种推广。
一维数组
存储结构
一维数组又称向量（Vector），它由一组具有相同类型的数据元素组成，并存储在一组连续的存储单元中。其存储结构如下图：
基本运算
对于可变长数组（Resizable Array）的插入、删除操作，其元素移动情况如下：
| 元素移动次数 （n 为数组大小, i 为操作位置） |
平均移动次数 | 时间复杂度 | |
|---|---|---|---|
| 插入 | $n-i+1$ 次 | $n/2$ 次 | O(n) |
| 删除 | $n-i$ 次 | $(n-1)/2$ 次 | O(n) |
二维数组
若一维数组中的数据元素又是一维数组结构，则称为二维数组，以此类推。一般地，一个 n 维数组可以看成元素为 n-1 维数组的线性表。
二维数组的地址计算（行优先）如下：
$$
loc[i,\ j]=loc[0,\ 0]+(n*i+j)*k
$$
其中，$i$ 为行坐标，$j$ 为列坐标，$n$ 为总列数，$k$ 为存储单元。
由公式可知，数组元素的存储位置是下标的线性函数。
矩阵（Matrix）是很多科学计算问题研究的对象，矩阵可以用二维数组来表示。
在数值分析中经常出现一些高阶矩阵，这些高阶矩阵中有许多值相同的元素或者零元素，如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。矩阵的非零元素个数很少的矩阵称为稀疏矩阵。
为了节省存储空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。
链表
存储结构
四种链表对比：
| 四种链表 | 非循环 | 循环（Cycle） |
|---|---|---|
| 单向（Singly） | 单向链表 | 单向循环链表 |
| 双向（Doubly） | 双向链表 | 双向循环链表 |
其中，是否循环的关键代码差异如下：
| 关键代码 | 非循环链表 | 循环链表 |
|---|---|---|
| 判断是否空链表 | head->next == NULL |
head->next == head |
| 判断是否尾结点 | p->next == NULL |
p->next == head |
基本运算
单链表插入（insert p before i）、删除（delete i）结点操作如下：
1 | // 单链表需要先找到 i - 1 结点以便进行插入、删除操作 |
注意：等号左边是指针，等号右边是结点。
双向循环链表插入（insert p after i）、删除（delete i）结点操作如下：
1 | // 双向循环链表直接获取 i 结点即可，因为可以通过其前驱、后继指针直接进行插入、删除操作 |
注意：等号左边是指针，等号右边是结点
栈
顺序存储结构
链式存储结构
基本运算
使用场景
队列
顺序存储结构
链式存储结构
基本运算
使用场景
数据结构系列（一）概论总结
引言
计算机解决一个具体问题时，一般需要经过以下几个步骤：
- 从具体的问题抽象出一个适当的数学模型；什么是数学模型呢？数学模型常常是现实世界的一个简化，是抽取对象的本质特性构造出来的。尽管数学是一门精准的科学，但是我们建立数学模型却要从实际出发，要针对问题做必要简化，简化的标准有两个：够用、易解。
- 设计一个求解该数学模型的算法；
- 用某种计算机编程语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解。
基本概念和术语
- 数据：所有被计算机存储、处理的对象。
- 数据对象：是性质相同的数据元素的集合，是数据的子集。
- 数据元素：数据的基本单位，也是运算的基本单位。例如在数据库中，又称为记录（Record）/元组（Tuple）。
- 数据项：数据不可分割的最小单位。例如在数据库中，又称为字段（Field）/域（Domain）。
- 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。它包括：
- 数据的逻辑结构
- 数据的存储结构
- 数据的基本运算
逻辑结构
https://en.wikipedia.org/wiki/Abstract_data_type
- https://en.wikipedia.org/wiki/Set_(abstract_data_type)
- https://en.wikipedia.org/wiki/List_(abstract_data_type)
- https://en.wikipedia.org/wiki/Tree_(data_structure)
- https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
集合结构
任意两个结点之间都没有邻接关系，组织形式松散：
集合的三大特性：
- 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。
- 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集，其中的元素允许出现多次。
- 无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序。
集合之间可以进行运算：
| 数学符号 | 含义 | 英文 |
|---|---|---|
| ∩ | 交 | Intersection |
| ∪ | 并 | Union |
| − | 差 | Difference |
线性结构
顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
特征：
- 排队（1:1）
- 起始节点无直接前驱
- 终端节点无直接后继
- 中间节点都有直接前驱和直接后继
树形结构
父子（1:N）
有没有想过为啥只有二叉树，而没有一叉树？实际上链表就是特殊的树，即一叉树。
图结构
地图（N:M）
存储结构
数据的逻辑结构在计算机中的实现，称为数据的存储结构（或物理结构）。
一般情况下，一个存储结构包括以下两个部分：
- 存储数据元素本身
- 数据元素之间的关联方式
逻辑结构常见的存储结构实现如下：
| 顺序存储方式 | 链式存储方式 | 散列存储方式 | 索引存储方式 | |
|---|---|---|---|---|
| 集合结构 | 散列表（Hash Table） | |||
| 线性结构 | 数组（一维、二维） 顺序栈 循环队列（取余运算） |
链表（单向/双向、是否循环） 链栈 链队列 |
||
| 树形结构 (二叉树) |
一维数组 |
链表 |
||
| 树形结构 (树) |
双亲表示法（一维数组） | 孩子链表表示法（一维数组 + 单链表） 孩子兄弟表示法（二叉链表，LC-RS） |
||
| 图结构 | 邻接矩阵（二维数组） | 邻接表（一维数组 + 单链表） |
顺序存储方式
所有存储结点存放在一个连续的存储区中。利用结点在存储区中的相对位置来表示数据元素之间的逻辑关系。
链式存储方式
每个存储结点除了含有一个数据元素之外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点。利用指针表示数据元素之间的逻辑关系。
散列存储方式
散列表（Hash Table）。
索引存储方式
基本运算
基本运算，是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。一般而言，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：等。
- 建立（Init）
- 读取（Access）
- 查找（Search）
- 插入（Insert）
- 删除（Delete）
算法
定义：一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能在有限时间内被求解。
算法分析：
- 正确性
- 易读性
- 健壮性
- 时空性
时间复杂度
空间复杂度
常用数据结构
参考
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Homebrew 包管理器总结
参考文档：https://brew.sh/
安装目录：/usr/local/Cellar
Homebrew
- Cask 通常用于安装一些带有图形界面的应用程序。
- Formulae 则是用于安装命令行工具和软件包的规则和脚本。
cask
常用的 cask：
1 | $ brew install --cask iterm2 |
formula
常用的 formula：
1 | $ brew install coreutils |
tap
MongoDB
https://www.mongodb.com/zh-cn/docs/manual/tutorial/install-mongodb-on-os-x/
https://github.com/mongodb/homebrew-brew
1 | $ brew tap mongodb/brew |
services
例子
1 | $ brew services start mysql@8.4 |
国内加速
Homebrew 源替换为 USTC 镜像：http://mirrors.ustc.edu.cn/help/brew.git.html
Homebrew 关闭自动更新：https://github.com/Homebrew/homebrew-autoupdate
1 | export HOMEBREW_NO_AUTO_UPDATE="1" |
参考
传输层常用工具总结——netstat、ss、lsof
ss
https://man7.org/linux/man-pages/man8/ss.8.html
1 | ss [options] [ FILTER ] |
例子
1 | # 列出当前 socket 统计信息 |
1 | # 统计指定进程 TCP 连接占用的端口 |
ss、netstat、lsof 命令的输出结果对比
netstat 是遍历 /proc 下面每个 PID 目录；
ss 直接读 /proc/net 下面的统计信息。所以 ss 执行的时候消耗资源以及消耗的时间都比 netstat 少很多。
netstat
https://en.wikipedia.org/wiki/Netstat
https://linux.die.net/man/8/netstat
例子
Linux 端口占用统计
1 | $ netstat -tanp | grep 7059 | tr -s ' ' | cut -d ' ' -f 4 | sort -n | uniq -c |
Mac 端口占用查询
1 | $ netstat -anv | grep 7059 |
Windows 端口占用查询
1 | # 查询占用了 8080 端口的[进程号]（最后一列） |
lsof
https://en.wikipedia.org/wiki/Lsof
https://linux.die.net/man/8/lsof
常用选项：
| 选项 | 描述 |
|---|---|
| -n | 不显示主机名（host name），显示 IP（network number）。例如 localhost 显示为 127.0.0.1 |
| -P | 不显示端口名（port name），显示端口号（port number）。例如 cslistener 显示为 9000 |
| -a | AND 运算 |
| -p s | 筛选指定 PID |
| -i […] | 筛选指定条件，例如：TCP + 端口号 |
| -s [p:s] | 筛选指定条件：例如：TCP (LISTEN) |
-i [
46][protocol][@hostname|hostaddr][:service|port]where:
46specifies the IP version, IPv4 or IPv6 that applies to the following address. ‘6‘ may be be specified only if the UNIX dialect supports IPv6. If neither ‘4‘ nor ‘6‘ is specified, the following address applies to all IP versions.protocolis a protocol name -TCP,UDPhostnameis an Internet host name. Unless a specific IP version is specified, open network files associated with host names of all versions will be selected.hostaddris a numeric Internet IPv4 address in dot form; or an IPv6 numeric address in colon form, enclosed in brackets, if the UNIX dialect supports IPv6. When an IP version is selected, only its numeric addresses may be specified.serviceis an /etc/services name - e.g.,smtpor a list of them.portis a port number, or a list of them.Here are some sample addresses:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-iTCP:25 - TCP and port 25
-i@1.2.3.4 - Internet IPv4 host address 1.2.3.4
-i@[3ffe:1ebc::1]:1234 - Internet IPv6 host address 3ffe:1ebc::1, port 1234
-iUDP:who - UDP who service port
-iTCP@lsof.itap:513 - TCP, port 513 and host name lsof.itap
-iTCP@foo:1-10,smtp,99 - TCP, ports 1 through 10, service name smtp, port 99, host name foo
-iTCP@bar:1-smtp - TCP, ports 1 through smtp, host bar
-i:time - either TCP, UDP or UDPLITE time service port
-s [p:s]
When followed by a protocol name (p), either
TCPorUDP, a colon (‘:’) and a comma-separated protocol state name list, the option causes open TCP and UDP files to be
- excluded if their state name(s) are in the list (s) preceded by a ‘^’;
or
- included if their state name(s) are not preceded by a ‘^’.
For example, to list only network files with
TCPstateLISTEN, use:
State names vary with UNIX dialects, so it’s not possible to provide a complete list. Some common TCP state names are:
CLOSED,IDLE,BOUND,LISTEN,ESTABLISHED,SYN_SENT,SYN_RCDV,ESTABLISHED,CLOSE_WAIT,FIN_WAIT1,CLOSING,LAST_ACK,FIN_WAIT_2, andTIME_WAIT.
例子
查询端口占用
1 | # 筛选条件：端口号 |
按 PID 查询
1 | # 查看某个进程的 open files，等价于 /proc/PID/fd/ |
lsof 输出结果每一列的含义：
COMMAND：进程的名称
PID：进程标识符
USER：进程所有者
FD：文件描述符，应用程序通过文件描述符识别该文件。如 cwd、txt 等
TYPE：文件类型，如 DIR、REG 等
DEVICE：指定磁盘的名称
SIZE：文件的大小
NODE：索引节点（文件在磁盘上的标识〉
NAME：打开文件的确切名称
参考
位运算及使用场景总结
| 二进制位运算 | 十进制运算 | |
|---|---|---|
& 按位与（AND） |
$M\&(n-1)$ | $M \bmod n$ |
| 按位或（OR） |
||
~ 按位非（NOT） |
||
^ 按位异或（XOR） |
||
<< 左位移（LEFT SHIFT） |
$M<<n$ | $M*2^n$ |
>> 右位移（RIGHT SHIFT） |
$M>>n$ | $M/2^n$ |
>>> 无符号右移 |
https://en.wikipedia.org/wiki/Mask_(computing)
Using a mask (bitmask) can be set
- either on or off,
- or inverted from on to off (or vice versa)
in a single bitwise operation.
「按位与 &」的使用场景
求子网地址
求子网地址（主机地址与子网掩码做按位与运算），参考：
例子：
实现循环队列
编程的时候，很多时候都会要求一个数在某一个范围内进行反复循环，例如实现循环队列。如果使用 if 语句，当判断达到最大值的时候回到开始处，效率较低。是否有更简单更高效的方法？
&按位与（AND）。比如说我想让一个数在 0-7 内循环，该如何做呢？temp = (temp++)&0x07，如此就简单的实现了 0-7 循环。因为要实现 0-7 的循环，其实只要提取一个变量递增的低三位即可。不管这个变量如何变化，它的低三位始终都是在 0-7 循环变化的。同理，它也可以实现 0-15、0-31 变化。但是这个方法有局限，它只能按照连续 bit 位的最大值进行循环。%取余运算（Modulo），它不存在上述限制。可以在 0-任意数循环。比如 0-5 循环，只要temp = (temp++)%6（注意是 6 而不是 5），那么 temp 就会在 0-5 之间循环了。
「按位或 |」的使用场景
单个变量保存多个值，节省存储空间
雪花算法的拼接
1 | timestamp << TIMESTAMP_SHIFT |
线程池的成员属性 ctl
线程池的成员属性 ctl，高 3 位表示 runState，低 29 位表示 workerCnt（按位或运算 bitwise OR）：
1 | runState workerCnt runState workerCnt |
操作系统 - 分页存储管理 - 逻辑地址结构
- 若用 $m$ 位表示逻辑地址，页大小为 $2^n$ 字节，则低 $n$ 位表示「页内偏移量」，高 $m-n$ 位表示「页号」。
- 例如 32 位的逻辑地址中，页大小为 $2^{12}$ (4KB)，则低 12 位表示「页内偏移量」，高 20 位表示「页号」。即：可用内存为「页号量 $2^{20}$」×「页大小 $2^{12}$ B」=「$2^{32}$ B」=「4 GB」
epoll_ctl() 的 event 参数
1 | EPOLLIN | EPOLLOUT | EPOLLRDHUP | EPOLLPRI | EPOLLERR | EPOLLHUP | EPOLLET | EPOLLONESHOT |
TCP - Header Format - Flags
Unix-like permissions
「按位异或 ^」的使用场景
前向纠错（FEC)）
TCP 协议实现可靠数据传输的 5 种措施中之一——差错控制，有两种纠错方案：
其中 FEC 的实质就是按位异或运算：
参考：https://www.jianshu.com/p/6157e120ef99
求 hash 值
求 hash 值使用了：
>>>无符号右移^按位异或&按位与
1 | int hash(Object key) { |
位移
逻辑右移可以处理除数为任意二的幂的除法，即：$M>>n$ 等于 $M/2^n$
更一般地，在特定底数 Base 的进位制中，除数（或分母）为任意 $Base^n$ 的除法（n 为整数）皆可以透过将数字位数向右移 n 位来完成。例如 除以十：
| $M/Base^n$ | Base 2 | Base 8 | Base 10 | Base 16 |
|---|---|---|---|---|
| 230 / 2 = 115 | 1110 0110 / 10 = 111 0011 | |||
| 230 / 8 = 28 | 346 / 10 = 34 | |||
| 230 / 10 = 23 | 230 / 10 = 23 | |||
| 230 / 16 = 14 | 0xE6 / 10 = 0xE |
参考
https://en.wikipedia.org/wiki/Bit
https://en.wikipedia.org/wiki/Bitwise_operation
https://en.wikipedia.org/wiki/Bit_array
https://dev.mysql.com/doc/refman/5.7/en/bit-functions.html
应用层 DNS 协议、相关命令总结
注册域名、管理资源记录（RR）都是站长/运维最常见的操作。本文总结了相关知识。
DNS 是什么？
DNS 是互联网的一项基础服务，它将人类易记的域名解析为不易记的 IP 地址，使人更方便的访问互联网。
DNS 的结构？
域名系统（DNS）是一个多层级、分布式的系统，就如同一个树状结构：
1 | +---+ |
| Domain types | DNS zone | Name server |
|---|---|---|
| Root domain 根域名 |
DNS root zone DNS 根区 |
Root name server 根域名服务器 |
| Top-level domain (TLD) 顶级域名 |
DNS zone | TLD name server 顶级域名服务器 |
| Second-level domain (SLD) 二级域名 |
DNS zone | Authoritative name server 权威域名服务器 |
| Sub domain 子域名 |
||
| Resource recerd, RR 资源记录 |
域名系统（DNS）的每一级只知道直接下级的位置，而无法获得跨级的位置，因此在域名解析的时候，需要自上而下、逐级查询。这种机制虽然看似低效，却能够提供分布式、高容错的服务，避免让域名系统（DNS）成为一个集中式的单点系统。
根域名（Root Domain）
早期的域名必须以英文句号“.”结尾，当用户访问 www.wikipedia.org 的 HTTP 服务时必须在地址栏中输入：http://www.wikipedia.org.，这样 DNS 才能够进行域名解析。如今 DNS 服务器已经可以自动补上结尾的句号。这个点 . 就是根域名。
. 代表的根域名服务器（Root name server），是 DNS 中最高级别的域名服务器（name server），负责返回顶级域名的权威域名服务器（Authoritative name server）的地址。
由于 ICANN 管理着所有的顶级域名，所以它是最高一级的域名节点。
根域名服务器（Root Name Server）
https://www.iana.org/domains/root/servers
由于早期的 DNS 查询结果是一个 512 字节的 UDP 数据包。这个包最多可以容纳 13 个服务器的地址，因此就规定全世界有 13 个根域名服务器，编号从
a.root-servers.net一直到m.root-servers.net：
HOSTNAME IP ADDRESSES OPERATOR a.root-servers.net 198.41.0.4, 2001:503:ba3e::2:30 Verisign, Inc. b.root-servers.net 199.9.14.201, 2001:500:200::b University of Southern California, Information Sciences Institute c.root-servers.net 192.33.4.12, 2001:500:2::c Cogent Communications d.root-servers.net 199.7.91.13, 2001:500:2d::d University of Maryland e.root-servers.net 192.203.230.10, 2001:500:a8::e NASA (Ames Research Center) f.root-servers.net 192.5.5.241, 2001:500:2f::f Internet Systems Consortium, Inc. g.root-servers.net 192.112.36.4, 2001:500:12::d0d US Department of Defense (NIC) h.root-servers.net 198.97.190.53, 2001:500:1::53 US Army (Research Lab) i.root-servers.net 192.36.148.17, 2001:7fe::53 Netnod j.root-servers.net 192.58.128.30, 2001:503:c27::2:30 Verisign, Inc. k.root-servers.net 193.0.14.129, 2001:7fd::1 RIPE NCC l.root-servers.net 199.7.83.42, 2001:500:9f::42 ICANN m.root-servers.net 202.12.27.33, 2001:dc3::35 WIDE Project 这 13 台根域名服务器由 12 个组织独立运营。其中，Verisign 公司管理两台根域名服务器：A 和 J。每家公司为了保证根域名服务器的可用性，会部署多个节点，比如单单 Verisign 一家公司就部署了 104 台根域名服务器（2016 年 1 月数据）。
所以，根域名服务器其实不止 13 台。据统计，截止 2016 年 1 月，全世界共有 517 台根域名服务器。你可以在 https://root-servers.org/ 这个网站查到所有根域名服务器的信息。
编号相同的根域名服务器使用同一个 IP，数百台根域名服务器总共只使用 13 个 IP（如上表所示），因此可以抵抗针对其所进行的分布式拒绝服务攻击（DDoS）。
根提示文件（Root Hints File）
https://www.internic.net/domain/named.root
根域名服务器虽然有 13 个域名，但是最少必须知道一台的 IP 地址，否则就会陷入循环查询。一般来说，本机都保存一份根域名服务器的 IP 地址的缓存，叫做 named.root 文件。这个文件同时记录了 13 台根域名服务器的 IP 地址。
2
3
4
5
6
7
8
9
A.ROOT-SERVERS.NET. 3600000 A 198.41.0.4
A.ROOT-SERVERS.NET. 3600000 AAAA 2001:503:ba3e::2:30
. 3600000 NS B.ROOT-SERVERS.NET.
B.ROOT-SERVERS.NET. 3600000 A 199.9.14.201
B.ROOT-SERVERS.NET. 3600000 AAAA 2001:500:200::b
...
参考：4.1 Address resolution mechanism
For proper operation of its domain name resolver, a network host is configured with an initial cache (hints) of the known addresses of the root name servers. The hints are updated periodically by an administrator by retrieving a dataset from a reliable source.
域名解析的循环依赖问题及其解决方案：4.3 Circular dependencies and glue records
Name servers in delegations are identified by name, rather than by IP address. This means that a resolving name server must issue another DNS request to find out the IP address of the server to which it has been referred. If the name given in the delegation is a subdomain of the domain for which the delegation is being provided, there is a circular dependency.
In this case, the name server providing the delegation must also provide one or more IP addresses for the authoritative name server mentioned in the delegation. This information is called glue. The delegating name server provides this glue in the form of records in the additional section of the DNS response, and provides the delegation in the authority section of the response. A glue record is a combination of the name server and IP address.
For example, if the authoritative name server for
example.orgisns1.example.org, a computer trying to resolvewww.example.orgfirst resolvesns1.example.org. Asns1is contained inexample.org, this requires resolvingexample.orgfirst, which presents a circular dependency. To break the dependency, the name server for the top level domain org includes glue along with the delegation forexample.org. The glue records are address records that provide IP addresses forns1.example.org. The resolver uses one or more of these IP addresses to query one of the domain’s authoritative servers, which allows it to complete the DNS query.
根区文件（Root Zone File）
https://www.internic.net/domain/root.zone
DNS 根域名服务器（Root name server）负责维护 DNS 根区文件（Root zone file）。该文件保存了所有顶级域名（TLD）的托管信息，所以非常大，超过 2MB。
举例来说，顶级域名
.com可以查到 13 个域名服务器：
2
3
4
5
6
7
8
9
10
11
12
13
com. 172800 IN NS b.gtld-servers.net.
com. 172800 IN NS c.gtld-servers.net.
com. 172800 IN NS d.gtld-servers.net.
com. 172800 IN NS e.gtld-servers.net.
com. 172800 IN NS f.gtld-servers.net.
com. 172800 IN NS g.gtld-servers.net.
com. 172800 IN NS h.gtld-servers.net.
com. 172800 IN NS i.gtld-servers.net.
com. 172800 IN NS j.gtld-servers.net.
com. 172800 IN NS k.gtld-servers.net.
com. 172800 IN NS l.gtld-servers.net.
com. 172800 IN NS m.gtld-servers.net.也就是说，
.com域名的解析结果，可以到这个 13 个服务器的任一台查询。细心的读者可能发现，这些服务器本身也是使用域名（比如a.gtld-servers.net.）标识，那么还得去查询它们指向的服务器，这样很容易造成循环查询。因此，DNS 根区文件还会同时提供这些服务器的 IP 地址（IPv4 和 IPv6）：
2
3
4
5
6
7
a.gtld-servers.net. 172800 IN AAAA 2001:503:a83e:0:0:0:2:30
b.gtld-servers.net. 172800 IN A 192.33.14.30
b.gtld-servers.net. 172800 IN AAAA 2001:503:231d:0:0:0:2:30
c.gtld-servers.net. 172800 IN A 192.26.92.30
c.gtld-servers.net. 172800 IN AAAA 2001:503:83eb:0:0:0:0:30
...理论上，所有域名查询都必须先查询根域名，因为只有根域名才能告诉你，某个顶级域名由哪个运营商、哪台服务器管理。事实上也确实如此，ICANN 维护着根区文件（Root zone file），里面记载着顶级域名和对应的记录。
但由于该文件很少变化，大多数 DNS 服务商都会提供它的缓存，所以根域名的查询事实上不是那么频繁。
根区数据库（Root Zone Database）
https://www.iana.org/domains/root/db
提供顶级域名的授权信息。
Much of this data is also available via the WHOIS protocol at whois.iana.org.
顶级域名（Top-Level Domain）
所有顶级域名保存在 Top-Level Domain List，可查询根区数据库（Root Zone Database）以获得更多信息（如顶级域名运营商信息、Name Servers）。
顶级域名（TLD）分为如下六种类型：
As of 2015, IANA distinguishes the following groups of top-level domains:[13]
Infrastructure top-level domain (ARPA): This group consists of one domain, the Address and Routing Parameter Area. It is managed by IANA on behalf of the Internet Engineering Task Force for various purposes specified in the Request for Comments publications.
Generic top-level domains (gTLD): Top-level domains with three or more characters
restricted generic top-level domains (grTLD): These domains are managed under official ICANN accredited registrars.
Sponsored top-level domains (sTLD): These domains are proposed and sponsored by private agencies or organizations that establish and enforce rules restricting the eligibility to use the TLD. Use is based on community theme concepts; these domains are managed under official ICANN accredited registrars.
country-code top-level domains (ccTLD): Two-letter domains established for countries or territories. With some historical exceptions, the code for any territory is the same as its two-letter ISO 3166 code.
- Internationalized country code top-level domains (IDN ccTLD): ccTLDs in non-Latin character sets (e.g., Arabic, Cyrillic, Hebrew, or Chinese).
- Test top-level domains (tTLD): These domains were installed under .test for testing purposes in the IDN development process; these domains are not present in the root zone.
其中下面两类是最常用的：
- 通用顶级域名（Generic top-level domain, gTLD），如常见的：
.com、.net、.org、.gov、… - 国家和地区顶级域名（Country code top-level domain, ccTLD），一般用两个字母的国家或地区名缩写代称，如：
.cn、.jp、…
顶级域名的数量仍在不断增长中，除了英文字母的域名，还不断新增各种语系的域名，如中文域名。
顶级域名服务器（TLD name server）
二级域名（Second-Level Domain）
组织或个人通过域名代理服务商（如 GoDaddy、万网）进行注册的域名。根据需要还可以自行在二级域名下新增三级、四级等子域名。
权威域名服务器（Authoritative name server）
https://en.wikipedia.org/wiki/Name_server#Authoritative_name_server
任何一个拥有域名的主机，其域名与 IP 地址的映射关系等信息都存储在权威域名服务器上。
资源记录（Resource Record）
域名系统中，一般一个域（DNS zone）通过一个 zone 文件保存该域的相关配置信息。zone 文件包含了域名和 IP 地址等资源之间的映射，以资源记录（Resource recerd, RR）的文本形式进行组织。
这里列举了所有的资源记录类型：
以域名 example.com 为例，其 zone 文件简化如下：
| name | ttl | record class | record type | record data | comment |
|---|---|---|---|---|---|
| example.com. | 1h | IN | NS |
ns | ns.example.com is a nameserver for example.com |
| ns | 1h | IN | A |
192.0.2.2 | IPv4 address for ns.example.com |
| example.com. | 1h | IN | A |
192.0.2.1 | IPv4 address for example.com |
| www | 1h | IN | CNAME |
example.com. | www.example.com is an alias for example.com |
CDN 服务常用到 CNAME 记录。
域名解析方式
参考 RFC 1034: Domain Names - Concepts and Facilities - IETF 规范的 2. INTRODUCTION - 2.3. Assumptions about usage 对于两种域名解析方式的描述：
In any system that has a distributed database, a particular name server may be presented with a query that can only be answered by some other server. The two general approaches to dealing with this problem are
- “recursive”, in which the first server pursues the query for the client at another server,
- “iterative”, in which the server refers the client to another server and lets the client pursue the query.
Both approaches have advantages and disadvantages, but the iterative approach is preferred for the datagram style of access. The domain system requires implementation of the iterative approach, but allows the recursive approach as an option.
迭代方式（Iterative Approach）
A DNS resolver that implements the iterative approach mandated by RFC 1034; in this case, the resolver consults three name servers to resolve the fully qualified domain name “www.wikipedia.org".
递归方式（Recursive Approach）
公共域名服务器
https://en.wikipedia.org/wiki/Public_recursive_name_server
DNS 相关命令
dig
安装
dig 命令安装：
1 | $ apt-get install dnsutils |
使用
dig 命令使用：https://downloads.isc.org/isc/bind9/cur/9.17/doc/arm/html/manpages.html#dig-dns-lookup-utility
1 | $ dig @name_server name record_type |
其中，record_type 参数如下：https://en.wikipedia.org/wiki/List_of_DNS_record_types
例子
dig 命令使用例子：
1 | # To use a specific DNS server for the query, use the @ option. |
1 | # By default, dig displays the A record for a domain. To look up a different DNS record, add it to the end of the command. |
1 | # query for any type of record information |
+[no]trace
This option toggles tracing of the delegation path from the root name servers for the name being looked up. Tracing is disabled by default. When tracing is enabled,
digmakes iterative queries to resolve the name being looked up. It follows referrals from the root servers, showing the answer from each server that was used to resolve the lookup.
下例中，使用公共域名服务器，而不是依次使用 /etc/resolv.conf 里配置的本地域名服务器进行 DNS 迭代查询，结果如下：
1 | $ dig @8.8.8.8 +trace www.google.com |
Wireshark 网卡抓包截图如下：DNS 协议 基于 UDP 协议，使用 53 端口。
nslookup
1 | $ nslookup www.google.com |
参考
RFC 1034: Domain Names - Concepts and Facilities - IETF
RFC 1035 - Domain names - implementation and specification
https://www.iana.org/domains/root
https://en.wikipedia.org/wiki/Domain_Name_System
https://en.wikipedia.org/wiki/Domain_name
https://wizardzines.com/comics/dig/