滴滴-测试开发面经（四）

一、.redis和mysql的区别总结

（1）类型上

        从类型上来说，mysql是关系型数据库，redis是缓存数据库

（2）作用上

       mysql用于持久化的存储数据到硬盘，功能强大，但是速度较慢

       redis用于存储使用较为频繁的数据到缓存中，读取速度快

（3）需求上

       mysql和redis因为需求的不同，一般都是配合使用。

二、详细说明

1.mysql和redis的数据库类型

mysql是关系型数据库，主要用于存放持久化数据，将数据存储在硬盘中，读取速度较慢。

redis是NOSQL，即非关系型数据库，也是缓存数据库，即将数据存储在缓存中，缓存的读取速度快，能够大大的提高运行效率，但是保存时间有限

2.mysql的运行机制

mysql作为持久化存储的关系型数据库，相对薄弱的地方在于每次请求访问数据库时，都存在着I/O操作，如果反复频繁的访问数据库。第一：会在反复链接数据库上花费大量时间，从而导致运行效率过慢；第二：反复的访问数据库也会导致数据库的负载过高，那么此时缓存的概念就衍生了出来。

3.缓存

缓存就是数据交换的缓冲区（cache），当浏览器执行请求时，首先会对在缓存中进行查找，如果存在，就获取；否则就访问数据库。

缓存的好处就是读取速度快

4.redis数据库

redis数据库就是一款缓存数据库，用于存储使用频繁的数据，这样减少访问数据库的次数，提高运行效率。

一、二叉搜索树特点

　　对于树中的每个节点X，它的左子树中所有关键字的值小于X的关键字值，而它的右子树中所有关键字值都大于X的关键字值

根据这个特性，对一个二叉树进行中序遍历，如果是单调递增的，则可以说明这个数二叉搜索树

重点操作有插入、删除

插入：

1、从根节点开始，遇键值较大则向左走，与键值较小则向右走，直至尾部，即插入点

删除：

1、如果存在于叶子节点，直接删除即可

2、删除的节点只有一个子节点，则将子节点连至父节点的即可（可以视为将子节点替换掉删除节点的位置）

3、删除的节点有两个子节点，这时需将右子树的最小值替换掉删除节点即可，最小节点可通过删除节点右子树一直向左走到底获得，

二、平衡二叉搜索树

发生的情况：当对二叉树进行插入或者删除的时候，有可能造成二叉搜索树失去平衡，造成搜寻效率低落的情况。

插入：

当向二叉搜索树插入一个节点分为ie四种情况

1、插入节点位于X的左子节点的左子树--左左

2、插入节点位于X的左子节点的右子树--左右

3、插入节点位于X的右子节点的左子树--右左

4、插入节点位于X的右子节点的右子树--右右

情况1、4彼此对称，称为外侧插入，采用单旋转操作即可调整

情况2、3彼此对称，称为内侧插入，可以采用双旋转（执行两次单旋转）操作调整

三、红黑树

红黑树不仅是一个二叉搜索树，还必须满足以下规则

1、每个节点不是红色就是黑色

2、根节点一定为黑色

3、如果节点是红色，则子节点必须为黑色

4、任一节点至NULL（树尾端）的任何路径，所含之黑节点树必须相同。

1 无名管道通信

无名管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

2 高级管道通信

高级管道(popen)：将另一个程序当做一个新的进程在当前程序进程中启动，则它算是当前程序的子进程，这种方式我们成为高级管道方式。

3 有名管道通信

有名管道 (named pipe) ：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

4 消息队列通信

消息队列( message queue ) ：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

5 信号量通信

信号量( semophore ) ：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

6 信号

信号 ( sinal ) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

7 共享内存通信

共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

8 套接字通信

套接字( socket ) ：套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

通信过程如下：

8.1命名socket

SOCK_STREAM 式本地套接字的通信双方均需要具有本地地址，其中服务器端的本地地址需要明确指定，指定方法是使用 struct sockaddr_un 类型的变量。

8.2 绑定

SOCK_STREAM 式本地套接字的通信双方均需要具有本地地址，其中服务器端的本地地址需要明确指定，指定方法是使用 struct sockaddr_un 类型的变量，将相应字段赋值，再将其绑定在创建的服务器套接字上，绑定要使用 bind 系统调用，其原形如下：

int bind(int socket, const struct sockaddr *address, size_t address_len);

其中 socket表示服务器端的套接字描述符，address 表示需要绑定的本地地址，是一个 struct sockaddr_un 类型的变量，address_len 表示该本地地址的字节长度。

8.3 监听

服务器端套接字创建完毕并赋予本地地址值（名称，本例中为Server Socket）后，需要进行监听，等待客户端连接并处理请求，监听使用 listen 系统调用，接受客户端连接使用accept系统调用，它们的原形如下：

int listen(int socket, int backlog);  int accept(int socket, struct sockaddr *address, size_t *address_len);

其中 socket 表示服务器端的套接字描述符；backlog 表示排队连接队列的长度（若有多个客户端同时连接，则需要进行排队）；address 表示当前连接客户端的本地地址，该参数为输出参数，是客户端传递过来的关于自身的信息；address_len 表示当前连接客户端本地地址的字节长度，这个参数既是输入参数，又是输出参数。

8.4 连接服务器

客户端套接字创建完毕并赋予本地地址值后，需要连接到服务器端进行通信，让服务器端为其提供处理服务。

对于SOCK_STREAM类型的流式套接字，需要客户端与服务器之间进行连接方可使用。连接要使用 connect 系统调用，其原型为

int connect(int socket, const struct sockaddr *address, size_t address_len);

其中socket为客户端的套接字描述符，address表示当前客户端的本地地址，是一个 struct sockaddr_un 类型的变量，address_len 表示本地地址的字节长度。实现连接的代码如下：

connect(client_sockfd, (struct sockaddr*)&client_address, sizeof(client_address));

8.5 相互发送接收数据

无论客户端还是服务器，都要和对方进行数据上的交互，这种交互也正是我们进程通信的主题。一个进程扮演客户端的角色，另外一个进程扮演服务器的角色，两个进程之间相互发送接收数据，这就是基于本地套接字的进程通信。发送和接收数据要使用 write 和 read 系统调用，它们的原型为：

int read(int socket, char *buffer, size_t len); int write(int socket, char *buffer, size_t len);

其中 socket 为套接字描述符；len 为需要发送或需要接收的数据长度；

对于 read 系统调用，buffer 是用来存放接收数据的缓冲区，即接收来的数据存入其中，是一个输出参数；

对于 write 系统调用，buffer 用来存放需要发送出去的数据，即 buffer 内的数据被发送出去，是一个输入参数；返回值为已经发送或接收的数据长度。

8.6 断开连接

交互完成后，需要将连接断开以节省资源，使用close系统调用，其原型为：

int close(int socket);