滴滴-測試開發(fā)面經(jīng)（四）

一、.redis和mysql的區(qū)別總結(jié)

（1）類型上

        從類型上來說，mysql是關(guān)系型數(shù)據(jù)庫，redis是緩存數(shù)據(jù)庫

（2）作用上

       mysql用于持久化的存儲數(shù)據(jù)到硬盤，功能強大，但是速度較慢

       redis用于存儲使用較為頻繁的數(shù)據(jù)到緩存中，讀取速度快

（3）需求上

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

二、詳細說明

1.mysql和redis的數(shù)據(jù)庫類型

mysql是關(guān)系型數(shù)據(jù)庫，主要用于存放持久化數(shù)據(jù)，將數(shù)據(jù)存儲在硬盤中，讀取速度較慢。

redis是NOSQL，即非關(guān)系型數(shù)據(jù)庫，也是緩存數(shù)據(jù)庫，即將數(shù)據(jù)存儲在緩存中，緩存的讀取速度快，能夠大大的提高運行效率，但是保存時間有限

2.mysql的運行機制

mysql作為持久化存儲的關(guān)系型數(shù)據(jù)庫，相對薄弱的地方在于每次請求訪問數(shù)據(jù)庫時，都存在著I/O操作，如果反復(fù)頻繁的訪問數(shù)據(jù)庫。第一：會在反復(fù)鏈接數(shù)據(jù)庫上花費大量時間，從而導(dǎo)致運行效率過慢；第二：反復(fù)的訪問數(shù)據(jù)庫也會導(dǎo)致數(shù)據(jù)庫的負載過高，那么此時緩存的概念就衍生了出來。

3.緩存

緩存就是數(shù)據(jù)交換的緩沖區(qū)（cache），當(dāng)瀏覽器執(zhí)行請求時，首先會對在緩存中進行查找，如果存在，就獲取；否則就訪問數(shù)據(jù)庫。

緩存的好處就是讀取速度快

4.redis數(shù)據(jù)庫

redis數(shù)據(jù)庫就是一款緩存數(shù)據(jù)庫，用于存儲使用頻繁的數(shù)據(jù)，這樣減少訪問數(shù)據(jù)庫的次數(shù)，提高運行效率。

一、二叉搜索樹特點

　　對于樹中的每個節(jié)點X，它的左子樹中所有關(guān)鍵字的值小于X的關(guān)鍵字值，而它的右子樹中所有關(guān)鍵字值都大于X的關(guān)鍵字值

根據(jù)這個特性，對一個二叉樹進行中序遍歷，如果是單調(diào)遞增的，則可以說明這個數(shù)二叉搜索樹

重點操作有插入、刪除

插入：

1、從根節(jié)點開始，遇鍵值較大則向左走，與鍵值較小則向右走，直至尾部，即插入點

刪除：

1、如果存在于葉子節(jié)點，直接刪除即可

2、刪除的節(jié)點只有一個子節(jié)點，則將子節(jié)點連至父節(jié)點的即可（可以視為將子節(jié)點替換掉刪除節(jié)點的位置）

3、刪除的節(jié)點有兩個子節(jié)點，這時需將右子樹的最小值替換掉刪除節(jié)點即可，最小節(jié)點可通過刪除節(jié)點右子樹一直向左走到底獲得，

二、平衡二叉搜索樹

發(fā)生的情況：當(dāng)對二叉樹進行插入或者刪除的時候，有可能造成二叉搜索樹失去平衡，造成搜尋效率低落的情況。

插入：

當(dāng)向二叉搜索樹插入一個節(jié)點分為ie四種情況

1、插入節(jié)點位于X的左子節(jié)點的左子樹--左左

2、插入節(jié)點位于X的左子節(jié)點的右子樹--左右

3、插入節(jié)點位于X的右子節(jié)點的左子樹--右左

4、插入節(jié)點位于X的右子節(jié)點的右子樹--右右

情況1、4彼此對稱，稱為外側(cè)插入，采用單旋轉(zhuǎn)操作即可調(diào)整

情況2、3彼此對稱，稱為內(nèi)側(cè)插入，可以采用雙旋轉(zhuǎn)（執(zhí)行兩次單旋轉(zhuǎn)）操作調(diào)整

三、紅黑樹

紅黑樹不僅是一個二叉搜索樹，還必須滿足以下規(guī)則

1、每個節(jié)點不是紅色就是黑色

2、根節(jié)點一定為黑色

3、如果節(jié)點是紅色，則子節(jié)點必須為黑色

4、任一節(jié)點至NULL（樹尾端）的任何路徑，所含之黑節(jié)點樹必須相同。

1 無名管道通信

無名管道( pipe )：管道是一種半雙工的通信方式，數(shù)據(jù)只能單向流動，而且只能在具有親緣關(guān)系的進程間使用。進程的親緣關(guān)系通常是指父子進程關(guān)系。

2 高級管道通信

高級管道(popen)：將另一個程序當(dāng)做一個新的進程在當(dāng)前程序進程中啟動，則它算是當(dāng)前程序的子進程，這種方式我們成為高級管道方式。

3 有名管道通信

有名管道 (named pipe) ：有名管道也是半雙工的通信方式，但是它允許無親緣關(guān)系進程間的通信。

4 消息隊列通信

消息隊列( message queue ) ：消息隊列是由消息的鏈表，存放在內(nèi)核中并由消息隊列標(biāo)識符標(biāo)識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。

5 信號量通信

信號量( semophore ) ：信號量是一個計數(shù)器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，防止某進程正在訪問共享資源時，其他進程也訪問該資源。因此，主要作為進程間以及同一進程內(nèi)不同線程之間的同步手段。

6 信號

信號 ( sinal ) ：信號是一種比較復(fù)雜的通信方式，用于通知接收進程某個事件已經(jīng)發(fā)生。

7 共享內(nèi)存通信

共享內(nèi)存( shared memory ) ：共享內(nèi)存就是映射一段能被其他進程所訪問的內(nèi)存，這段共享內(nèi)存由一個進程創(chuàng)建，但多個進程都可以訪問。共享內(nèi)存是最快的 IPC 方式，它是針對其他進程間通信方式運行效率低而專門設(shè)計的。它往往與其他通信機制，如信號量，配合使用，來實現(xiàn)進程間的同步和通信。

8 套接字通信

套接字( socket ) ：套接口也是一種進程間通信機制，與其他通信機制不同的是，它可用于不同機器間的進程通信。

通信過程如下：

8.1命名socket

SOCK_STREAM 式本地套接字的通信雙方均需要具有本地地址，其中服務(wù)器端的本地地址需要明確指定，指定方法是使用 struct sockaddr_un 類型的變量。

8.2 綁定

SOCK_STREAM 式本地套接字的通信雙方均需要具有本地地址，其中服務(wù)器端的本地地址需要明確指定，指定方法是使用 struct sockaddr_un 類型的變量，將相應(yīng)字段賦值，再將其綁定在創(chuàng)建的服務(wù)器套接字上，綁定要使用 bind 系統(tǒng)調(diào)用，其原形如下：

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

其中 socket表示服務(wù)器端的套接字描述符，address 表示需要綁定的本地地址，是一個 struct sockaddr_un 類型的變量，address_len 表示該本地地址的字節(jié)長度。

8.3 監(jiān)聽

服務(wù)器端套接字創(chuàng)建完畢并賦予本地地址值（名稱，本例中為Server Socket）后，需要進行監(jiān)聽，等待客戶端連接并處理請求，監(jiān)聽使用 listen 系統(tǒng)調(diào)用，接受客戶端連接使用accept系統(tǒng)調(diào)用，它們的原形如下：

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

其中 socket 表示服務(wù)器端的套接字描述符；backlog 表示排隊連接隊列的長度（若有多個客戶端同時連接，則需要進行排隊）；address 表示當(dāng)前連接客戶端的本地地址，該參數(shù)為輸出參數(shù)，是客戶端傳遞過來的關(guān)于自身的信息；address_len 表示當(dāng)前連接客戶端本地地址的字節(jié)長度，這個參數(shù)既是輸入?yún)?shù)，又是輸出參數(shù)。

8.4 連接服務(wù)器

客戶端套接字創(chuàng)建完畢并賦予本地地址值后，需要連接到服務(wù)器端進行通信，讓服務(wù)器端為其提供處理服務(wù)。

對于SOCK_STREAM類型的流式套接字，需要客戶端與服務(wù)器之間進行連接方可使用。連接要使用 connect 系統(tǒng)調(diào)用，其原型為

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

其中socket為客戶端的套接字描述符，address表示當(dāng)前客戶端的本地地址，是一個 struct sockaddr_un 類型的變量，address_len 表示本地地址的字節(jié)長度。實現(xiàn)連接的代碼如下：

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

8.5 相互發(fā)送接收數(shù)據(jù)

無論客戶端還是服務(wù)器，都要和對方進行數(shù)據(jù)上的交互，這種交互也正是我們進程通信的主題。一個進程扮演客戶端的角色，另外一個進程扮演服務(wù)器的角色，兩個進程之間相互發(fā)送接收數(shù)據(jù)，這就是基于本地套接字的進程通信。發(fā)送和接收數(shù)據(jù)要使用 write 和 read 系統(tǒng)調(diào)用，它們的原型為：

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

其中 socket 為套接字描述符；len 為需要發(fā)送或需要接收的數(shù)據(jù)長度；

對于 read 系統(tǒng)調(diào)用，buffer 是用來存放接收數(shù)據(jù)的緩沖區(qū)，即接收來的數(shù)據(jù)存入其中，是一個輸出參數(shù)；

對于 write 系統(tǒng)調(diào)用，buffer 用來存放需要發(fā)送出去的數(shù)據(jù)，即 buffer 內(nèi)的數(shù)據(jù)被發(fā)送出去，是一個輸入?yún)?shù)；返回值為已經(jīng)發(fā)送或接收的數(shù)據(jù)長度。

8.6 斷開連接

交互完成后，需要將連接斷開以節(jié)省資源，使用close系統(tǒng)調(diào)用，其原型為：

int close(int socket);