8---innodb的list算法 · 思考mysql內核之初級系列

在上一篇里，bingxi和alex聊了下關于hash表的內容。在本篇里，會聊下關于list的內容。所謂list，就是雙向鏈表，這樣的算法在《數據結構》里面都是常見的。為了屏蔽差異性，類似于hash表，mysql將list通過宏來實現。對應的文件為： D:/mysql-5.1.7-beta/storage/innobase/include/ut0lst.h ## 1)常用結構體 Alex：“bingxi，考你一個問題：如果共享空間有4個文件，這四個文件是如何連在一起的。我們在ut0lst.h中看到了這樣一段注釋： /* This module implements the two-way linear list which should be used if a list is used in the database. Note that a single struct may belong to two or more lists, provided that the list are given different names. An example of the usage of the lists can be found in fil0fil.c. */ 在注釋中有提到fil0fil.c，那么我就問你共享空間的這個文件組織方式。 ” Bingxi：“要掌握這個具體怎么實現，我們還是需要進行調試。在調試之前，我們先從這段文字中看出幾個有用的信息，然后再去驗證它。1）這是一個雙向鏈表，因此插入的時候有prev和next指針，2）一個結構體可能會屬于多個list。我們先來驗證這兩個信息。看fil_node_struct的定義，該結點屬于兩個list，一個對應的是文件list，另外一個是LURlist。 ~~~ /* File node of a tablespace or the log data space */ struct fil_node_struct { ?????? …… ?????? UT_LIST_NODE_T(fil_node_t) chain;? //屬于文件list ?????? UT_LIST_NODE_T(fil_node_t) LRU;??? //屬于LRUlist ? …… }; ~~~ 我們再看一下UT_LIST_NODE_T的定義，如下： ~~~ #define UT_LIST_NODE_T(TYPE)/ struct {/ ?????? TYPE *?? prev;?????? /* pointer to the previous node,/ ???????????????????? NULL if start of list *// ?????? TYPE *?? next;?????? /* pointer to next node, NULL if end of list *// }/ ~~~ 從這個定一個中，我們可以看到一個prev指針指向前一個結點，一個next指針指向下一個結點。我們再來替代法來進行簡化，將fil_node_struct中宏定義進行替代。替代后為： ~~~ typedef??? struct fil_node_struct???? fil_node_t; /* File node of a tablespace or the log data space */ struct fil_node_struct { ?????? …… ?????? struct { ?????? fil_node_t *??? prev;?????? /* pointer to the previous node, ???????????????????? NULL if start of list */ ?????? fil_node_t *??? next;?????? /* pointer to next node, NULL if end of list */ ? }chain； ?????? struct { ?????? fil_node_t *??? prev;?????? /* pointer to the previous node, ???????????????????? NULL if start of list */ ?????? fil_node_t *??? next;?????? /* pointer to next node, NULL if end of list */ ?}LRU; ? …… }; ~~~ 這樣的，就好辦了，取得chain的下一個結點，就是： (node->chain).next（其中fil_node_t* node）。假設是共享表空間里面有4個文件，那么啟動之后，鏈表是什么情況？ ” Alex：“ok，這個我們就來debug一下。debug之前我們要先看下，file_space_struct中的一個結構成員：chain。共享表空間對應的4個文件會掛在上面，然后每個file_node_t結構通過prev和next進行雙向連接。 ~~~ typedef??? struct fil_node_struct???? fil_node_t; /* Tablespace or log data space: let us call them by a common name space */ struct fil_space_struct { ?????? …… ?????? UT_LIST_BASE_NODE_T(fil_node_t) chain; ?????? …… }; ~~~ 我們要看一下UT_LIST_BASE_NODE_T的定義： ~~~ #define UT_LIST_BASE_NODE_T(TYPE)/ struct {/ ?????? ulintcount;???? /* count of nodes in list *// ?????? TYPE *?? start;?????? /* pointer to list start, NULL if empty *// ?????? TYPE *?? end;/* pointer to list end, NULL if empty *// }/ ~~~ 同樣的，我們進行替換。會得到如下的情況： ~~~ typedef??? struct fil_node_struct???? fil_node_t; /* Tablespace or log data space: let us call them by a common name space */ struct fil_space_struct { ?????? …… ?????? struct { ?????? ulintcount;???? /* count of nodes in list */ ?????? fil_node_t *??? start;?????? /* pointer to list start, NULL if empty */ ?????? fil_node_t *??? end;/* pointer to list end, NULL if empty */ ? } chain; ?????? …… }; ~~~ 從中我們得到第一個list成員，最后一個list成員，以及該list的成員數量。如果我們需要取得第一個成員就是： fil_space_t*??? space; fil_node_t*???? node; …… node=(space->chain).start?? //這個已經通過宏來實如果要取得再下一個，就是(node->chain).next（這個已經通過宏來實現）。我們接著通過debug進行驗證，配置my.ini（本例路徑為D:/mysql-5.1.7-beta/my.ini，也可以存放在其它路徑）。修改表空間，使用共享表空間為4個文件： [mysqld] innodb_data_file_path = ibdata1:10M;ibdata2:20M;ibdata3:30M;ibdata4:40M:autoextend 將D:/mysql-5.1.7-beta/data里面的內容恢復到初始化，所謂的初始化也就是將一開始代碼解壓縮時產生的原始data目錄進行保存。需要初始化數據時，用該文件夾數據替代D:/mysql-5.1.7-beta/data的數據。在fil_node_create函數設置斷點，每執行一次看一次成員變量，等共享表空間對應的4個文件都執行之后我們可以看下該space對應的chain對應的取值。見圖1: ![](https://box.kancloud.cn/2016-07-22_5791c9c1326ec.gif) 從圖1中，我們可以看出4個結點通過prev及next指針相連，通過space->chain我們可以找到第一個結點，和最后一個結點。在圖形中，通過天藍色的線條表示prev。通過這樣的一個圖形，我們會對list的表達方式有一個整體的了解。下面我們，在看一些具體函數的實現方式。 ” ## 2）常用的函數 Bingxi：“好的，我們來看下插入函數吧。在圖1中，我有一個疑問，問什么第一個成員的prev指向的是null，而不是指向space。” Alex：“贊同，我們還是通過剛剛的例子來看下常用的插入函數UT_LIST_ADD_LAST，這個函數是往鏈表的末尾插入一個值。我們先看下該函數的定義，先不看其中的實現： ~~~ /*********************************************************************** Adds the node as the last element in a two-way linked list. BASE has to be the base node (not a pointer to it). N has to be the pointer to the node to be added to the list. NAME is the list name. */ #define UT_LIST_ADD_LAST(NAME, BASE, N)/ {/ ?????? ut_ad(N);/ ?????? ((BASE).count)++;/ ?????? ((N)->NAME).prev = (BASE).end;/ ?????? ((N)->NAME).next = NULL;/ ?????? if ((BASE).end != NULL) {/ ????????????? (((BASE).end)->NAME).next = (N);/ ?????? }/ ?????? (BASE).end = (N);/ ?????? if ((BASE).start == NULL) {/ ????????????? (BASE).start = (N);/ ?????? }/ }/ ~~~ 插入文件結點的調用方式如下： ~~~ fil_node_t*???? node; …… UT_LIST_ADD_LAST(chain, space->chain, node); ? 進行宏的替換，用下面的偽碼表示： fil_node_t*???? node; void ut_list_add_last(chain, space->chain, node) { ?????? ut_ad(node);?? //斷言語句 ?????? ((space->chain).count)++;?? //步驟1：將列表的成員數量+1 ?????? ?????? //步驟2：設置插入結點的prev和next指針 ?????? //因為是插入到最后一個結點，所以next指針設置為null ?????? //prev設置為插入前鏈表的最后一個結點，如果鏈表為空：(BASE).end為也為空，所以第一個結點成員的prev為空 ?????? ((node)->chain).prev = (space->chain).end; ?????? ((node)->chain).next = NULL;/ ?????? //步驟3：如果插入鏈表結點不為空，則將node結點掛在已經結點的后面 ?????? if ((space->chain).end != NULL) { ????????????? (((space->chain).end)->chain).next = (node); //原來的最后一個結點的next指向新的結點 ?????? } ?????? //步驟4：重新設置space->chain的end和start結點 ?????? //end結點很容易理解，就是指向新插入的結點，因為我們的操作就是插入到最后一個結點 ?????? //start的就要確認了：如果之前結點為空，則start也指向該結點，因為插入后只有一個結點，start和end都指向它 ?????? //如果start結點之前不為空，也就是鏈表有成員，將新成員插入到末尾的操作不影響start指針 ?????? (space->chain).end = (node); ?????? if ((space->chain).start == NULL) { ????????????? (space->chain).start = (node); ?????? } } ~~~ ” Bingxi：“贊同你的看法，不過你少講了一個內容，鏈表在創建的時候會進行初始化， ~~~ UT_LIST_INIT(space->chain);? //函數調用 …… #define UT_LIST_INIT(BASE)/ {/ ?????? (BASE).count = 0;/ ?????? (BASE).start = NULL;/ ?????? (BASE).end?? = NULL;/ }/ ~~~ 將鏈表的count設置為0，start和end設置為null。另外，我發現alex最喜歡用代入法這樣的傻方法，通過代入的方式來解釋宏的實現，這也太傻了吧，哈哈。 ” Alex：“有時候，這樣的方法也挺有效的，呵呵。第一次使用的時候可以用這樣的方法先理解下，然后再看會簡單些。我們現在直接看下類似的插入到鏈表首的宏的實現，這次我們直接看，不用代入法。 ~~~ /*********************************************************************** Adds the node as the first element in a two-way linked list. BASE has to be the base node (not a pointer to it). N has to be the pointer to the node to be added to the list. NAME is the list name. */ #define UT_LIST_ADD_FIRST(NAME, BASE, N)/ {/ ?????? ut_ad(N);/ ?? ?//步驟1：將列表的成員數量+1 ?????? ((BASE).count)++;/ ? //步驟2，設置插入結點的prev和next指針 //因為是插入到首結點，所以該結點的prev為null //新插入結點的next指向原鏈表的首結點 //這樣就完成了新結點的prev和next指針的設置 ?????? ((N)->NAME).next = (BASE).start;/ ?????? ((N)->NAME).prev = NULL;/ //步驟3：如果插入前鏈表結點不為空，則原首結點的prev要進行重新設置 //將原首結點的prev指向新的結點 ?????? if ((BASE).start != NULL) {/ ????????????? (((BASE).start)->NAME).prev = (N);/ ?????? }/ ??? //步驟4：重新設置space->chain的end和start結點 ?????? //start指針很容易理解，因為我們是插入到鏈表首，所以該結點就是首結點 //同樣的，如果插入前鏈表為空，也就是插入前end為空，則需要將end也指向這個唯一的鏈表成員 //如果插入前鏈表不為空，則不需要修改end指針。 (BASE).start = (N);/ ?????? if ((BASE).end == NULL) {/ ????????????? (BASE).end = (N);/ ?????? }/ }/ ~~~ 另外有兩個類似的宏，bingxi來看一下：UT_LIST_INSERT_AFTER、UT_LIST_REMOVE。 ” Bingxi：“這兩個宏就不用看了吧，都是些鏈表的算法。留給大家自己看下吧。除了這兩個宏之外，還有三個最基本的宏，用于獲取base_node的三個成員：count、start、end。這里我把定義貼一下： ~~~ /************************************************************************ Alternative macro to get the number of nodes in a two-way list, i.e., its length. BASE is the base node (not a pointer to it). */ #define UT_LIST_GET_LEN(BASE)/ ?????? (BASE).count /************************************************************************ Gets the first node in a two-way list, or returns NULL, if the list is empty. BASE is the base node (not a pointer to it). */ #define UT_LIST_GET_FIRST(BASE)/ ?????? (BASE).start /************************************************************************ Gets the last node in a two-way list, or returns NULL, if the list is empty. BASE is the base node (not a pointer to it). */ #define UT_LIST_GET_LAST(BASE)/ ?????? (BASE).end ~~~ ” Alex：“嗯，這三個成員的比較簡單。這一篇和上一篇，我們聊了兩個基本算法結構，下一篇我們還會說一下動態數組。在第十篇寫完之后，bingxi公布個list吧。將要開始寫到innodb的文件存儲內部格式，以及組織方法了。” Bingxi：“好的，我回去想一下，第十篇出來后，就給你提供一個list，列出段、簇、頁、記錄等等的物理存儲格式以及相互關系，然后按照list的組織方式來往下思考。” Alex：“ok”