Jepson's Blog

b树

b树就是平衡M叉树。跟平衡二叉树类似，avl的非叶子节点只有一个关键字，b树的非叶子节点有M-1个关键字。M-1个关键字将数据划分为M段，每个儿子节点对应一段。b树的叶子结点和非叶子节点都存放数据。

一个M阶的b树具有如下几个特征：

• 定义任意非叶子结点最多只有M个儿子，且M>2；
• 根结点的儿子数为[2, M]；
• 除根结点以外的非叶子结点的儿子数为[M/2, M]，向上取整；
• 非叶子结点的关键字个数=儿子数-1；
• 所有叶子结点位于同一层；
• k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系。

有关b树的一些特性，注意与后面的b+树区分：

• 关键字集合分布在整颗树中；
• 任何一个关键字出现且只出现在一个结点中；
• 搜索有可能在非叶子结点结束；
• 其搜索性能等价于在关键字全集内做一次二分查找；

b+树

b+树是b树的变体，区别是b+树非叶子节点有M个关键字，并且不在非叶子结点存储数据，同时b+树的叶子结点之间也有指针相连。

M阶的b+树的特征：

• 有M棵子树的非叶子结点中含有M个关键字（b树是M-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）。
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
• 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
• 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。

b+树相比于b树的查询优势：

• b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
• b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
• 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历;

浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。

真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。

b+树的查找过程

如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。

真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

从IO的角度来说B+树的复杂度是O(log_mN)

http是超文本传输协议，服务器和浏览器之间的数据传输使用的是明文传输，所以很不安全。

https就是在http的基础上增加安全套接字层SSL(sercue socket layer)，使用SSL对服务器和浏览器之间的数据传输进行加密。

第一阶段：建立安全能力

客户端-client_hello：

• 客户端可以支持的SSL最高版本号;
• 客户端生成的32字节的随机数;
• 会话标识符ID;
• 客户端可以支持的密码套件列表;
• 客户端可以支持的压缩方法列表。

服务端-server_hello：

• SSL版本号，取收到的客户端SSL版本和服务端支持的最高版本中的较低者;
• 服务端生成的32字节的随机数;
• 会话标识符ID;
• 从收到的客户端密码套件列表中选择一个密码套件(包含密钥交换算法、对称加密算法、摘要算法);
• 从收到的客户端压缩方法列表中选择一种压缩方法。

第二阶段：服务端验证和密钥交换

服务端-certificate：

• 含有公钥信息的服务端数字证书或到CA的完整证书链。

服务端-server_key_exchange：

• 可选，根据密钥协商算法而定，如果传送给客户端的服务端证书数据不足以按照第一阶段选定的密钥交换算法协商密钥，该步骤不足密钥协商元素。

服务端-certificate_request：

• 可选，请求验证客户端证书信息，单向数据认证(只认证服务端)无此步骤。

服务端-server_hello_done：

• 通知客户端版本号和加密套件协商结束。

第三阶段：客户端验证和密钥交换

客户端-certificate：

• 可选，客户端数字证书，双向数据认证中服务端要求验证客户端身份合法性。

客户端-client_key_exchange：

• 客户端交换密钥，视密钥交换算法而定，密钥协商参数或pre-master key(服务端公钥加密)。

客户端-certificate_verify：

• 可选，客户端将已交互的握手消息、会话密钥的摘要值用客户端私钥加密发送给服务端。

第四阶段：完成

客户端-change_cipher_spec：

• 改变密码格式信息，告诉服务端之后的报文消息用会话密钥加密。

客户端-finished：

• 向服务端宣布握手协议完成。

服务端-change_cipher_spec：

• 改变密码格式信息，告诉客户端之后的报文消息用会话密钥加密。

服务端-finished：

• 向客户端宣布握手协议完成。

C++ STL里的优先队列priority_queue底层时用堆实现的。

使用时简单的小顶堆/大顶堆可以如下定义：

1
2
3

priority_queue<int,vector<int>,greater<int> > q;  //小顶堆

priority_queue<int,vector<int>,less<int> > q;  //大顶堆

但是greater和less只适用于简单的元素类型，对于复杂元素（比如自定义的结构体）需要重载运算符<。

1
2
3
4
5
6
7

struct node{
    int num;
    int dis;
    bool operator <(const node &a) const{
        return a.dis<dis; // 小顶堆
    }
};

算法变革：BFS->Dijkstra->A*

BFS

1162. 地图分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void BFS(){
    int x, y, z;
    int nx, ny, nz;
    while(!que.empty()){
        z = que.front();
        que.pop();
        vis[z] = true;
        x = z/n;
        y = z%n;
        for(int i=0;i<4;i++){
            nx = x+dir[i][0];
            ny = y+dir[i][1];
            nz = nx*n+ny;
            if(nx>=0&&nx<n&&ny>=0&&ny<n&&!mp[nx][ny]&&!vis[nz]&&dis[nz]>dis[z]+1){
                dis[nz] = dis[z] + 1;
                que.push(nz);
            }
        }
        ans = dis[z];
    }
}

BFS只能用来解决无权图的最短路问题。

Dijkstra

743. 网络延迟时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void Dijkstra(){

    int mx = 0;
    dis[0] = 0x3f3f3f3f; 

    for(int i=1;i<=m;i++){
        mx = 0;
        for(int j=1;j<=m;j++){
            if(!vis[j]&&dis[j]<dis[mx]){
                mx = j;
            }
        }
        if(mx==0) break;

        vis[mx] = true;

        for(int j=1;j<=m;j++){
            if(!vis[j]&&dis[j]>dis[mx]+mp[mx][j]){
                dis[j] = dis[mx] + mp[mx][j];
            }
        }
        ans = max(ans, dis[mx]);
    }
}

Dijkstra可以解决带权图的最短路问题，但是普通版Dijkstra的时间复杂度是O(N^2)的，可以使用堆优化来降低复杂度。

堆优化Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

struct node{
    int num;
    int dis;
    bool operator <(const node &a) const{
        return a.dis<dis;
    }
};
void Dijkstra(){

    priority_queue<node> que;
    for(int j=1;j<=m;j++){
        if(dis[j]==0){
            que.push(node{j,0});
        }
    }

    while(!que.empty()){
        node tmp = que.top();
        int u = tmp.num;
        que.pop();
        if(vis[u]) continue;
        vis[u] = true;

        for(int j=1;j<=m;j++){
            if(!vis[j]&&dis[j]>dis[u]+mp[u][j]){
                dis[j] = dis[u] + mp[u][j];
                que.push(node{j,dis[j]});
            }
        }
        ans = max(ans, dis[u]);
    }
}

堆优化就是把每次寻找优先级最高的节点的操作用一个小顶堆代替，复杂度为O(nlogn)。

BestFirst(最佳优先搜索)

BestFirst就是把未搜索节点的优先级定义为该节点与目标节点之间的估计距离，如果这个估计距离刚好是真实距离，则BestFirst可以很快搜索到目标节点，但是大多数情况下估计距离时不准确的。这个估计距离是非常启发式的，比如曼哈顿距离等。如果估计距离设定的不准确，那么很可能得到的最短路是错误的。

A*

A*结合了Dijkstra和BestFirst，关键的区别也是对未搜索节点的优先级定义。A*将优先级定义为：f(n) = g(n) + h(n)。其中g(n)是该节点到其实节点的距离，h(n)是一个启发式函数表示该节点到目标节点之间的估计距离。

在极端情况下，如果h(n)=0则A*退化为Dijkstra，如果g(n)=0则A*退化为BestFirst。

如果h(n)小于该节点到目标节点的实际距离，则A*一定能找到最短路，但是h(n)越小，搜索的节点就越多，导致算法就越慢；

如果h(n)刚好等于该节点到目标节点的实际距离，则A*会以很快的速度找到最短路，但是在现实中很难找到这样的h(n);

如果h(n)大于该节点到目标节点的实际距离，则A*不一定能找到最短路，不过此时算法的速度会很快。