南昌公司做网站需要多少钱中山优秀网站建设
1. 关于索引组织表
InnoDB使用的是索引组织表(IOT)的方式存储表记录，索引组织表以主键构建一个B-tree的数据结构来存储行记录，行记录存储在树的叶节点内。这与Oracle数据库是不同的，Oracle数据库默认创建的表是堆组织表(HOT)，HOT记录按堆数据结构进行存储。在InnoDB中，我们将存储行记录的B-tree索引称为Clustered Index, 而表的相关普通B-tree索引(非主键索引)称为Secondary Index。
The data in each table is divided into pages. The pages that make up each table are arranged in a tree data structure called a B-tree index. Table data and secondary indexes both use this type of structure. The B-tree index that represents an entire table is known as the clustered index, which is organized according to the primary key columns. The nodes of a clustered index data structure contain the values of all columns in the row. The nodes of a secondary index structure contain the values of index columns and primary key columns.
存储Clustered Index的节点(页)与Secondary Index的的节点的内容是不一样的，树结构，包含页节点(Leaf)和非叶节点(Non-Leaf)，前文提到，InnoDB中表的记录和相关索引都使用FIL_PAGE_INDEX Page存储，要解析一个FIL_PAGE_INDEX页的第一步就是要确定这个页存储的是什么数据。
1. FIL_PAGE_INDEX Page的结构
前文提到，表和其相关索引的数据是存储在FIL_PAGE_INDEX页的，那么我们首先看看FIL_PAGE_INDEX的页结构：
0+--------------------------+| FIL Header (38) |38+--------------------------+| INDEX Header (36) |74+--------------------------+| FSEG Header (20) |94+--------------------------+| System Records (26) |120+--------------------------+| User Records | // Records are un-ordered physically, 物理无序(不按主键顺序)存放, 类似于堆表| | // 但会由一个单向链表(singly-linked)将用户记录按主键有序串起来。+--------Heap Top----------+ // Heap Top是Page空间使用的高水位(HWM)| Free Space |+--------------------------+| Page Directory | // The page directory grows downwards from the FIL trailer in ascending order by key. //空间占用从后往前增长| | // The number of entries is stored in the INDEX header. 数量记录在INDEX Header->PAGE_N_DIR_SLOTS中。
16376+--------------------------+| FIL Trailer (8) |
16384+--------------------------+
* 前面的数字是在Page内的偏移(bytes)
解析的第一步需要解析FIL_PAGE_INDEX的INDEX_Header结构:
38 +----------------------+ | PAGE_N_DIR_SLOTS (2) |
40 +----------------------+| PAGE_HEAP_TOP (2) |
42 +----------------------+| PAGE_N_HEAP (2) |
46 +----------------------+| PAGE_FREE (2) |
48 +----------------------+ | PAGE_GARBAGE (2) |
50 +----------------------+| PAGE_LAST_INSERT (2) |
52 +----------------------+| PAGE_DIRECTION (2) |
52 +----------------------+| PAGE_N_DIRECTION (2) |
54 +----------------------+| PAGE_N_RECS (2) |
56 +----------------------+| PAGE_MAX_TRX_ID (2) |
64 +----------------------+| PAGE_LEVEL (2) |
66 +----------------------+ | PAGE_INDEX_ID (2) |
73 +----------------------+ * 前面的数字是在Page内的偏移(bytes)
通过解析INDEX_Header，我们就可以知道FIL_PAGE_INDEX存储的是哪个索引，记录类型，page level, …：
public class IdxPage1 {public static void main(String[] args) throws IOException, Exception {String fileName = "D:\\Data\\mysql\\8.0.18\\data\\sakila\\film.ibd";try (IbdFileParser parser = new IbdFileParser(fileName)) {List<Long> pageNums = parser.getPageTypeMap().get(FilHeader.FIL_PAGE_INDEX);StringBuilder buff = new StringBuilder();buff.append(" PAGE PAGE_TYPE LEVEL INDEX_ID PAGE_PREV PAGE_NEXT\n").append("----- --------------- ----- -------- ----------- -----------\n");for (long pageNum : pageNums) {IndexPage indexPage = (IndexPage) parser.getPage(pageNum);FilHeader filHeader = indexPage.getFilHeader();IndexHeader indexHeader = indexPage.getIndexHeader();buff.append(String.format("%5d ", pageNum)).append(String.format("%15s ", filHeader.getPageTypeName())).append(String.format("%5d ", indexHeader.getPageLevel())).append(String.format("%8d ", indexHeader.getIndexId())).append(String.format("%11d ", filHeader.getPreviousPage())).append(String.format("%11d ", filHeader.getNextPage())).append("\n");}System.out.println(buff);}}
}
程序输入:PAGE PAGE_TYPE LEVEL INDEX_ID PAGE_PREV PAGE_NEXT
----- --------------- ----- -------- ----------- -----------4 FIL_PAGE_INDEX 1 596 4294967295 4294967295 5 FIL_PAGE_INDEX 1 597 4294967295 4294967295 6 FIL_PAGE_INDEX 0 598 4294967295 4294967295 7 FIL_PAGE_INDEX 0 599 4294967295 4294967295 8 FIL_PAGE_INDEX 0 596 4294967295 9 9 FIL_PAGE_INDEX 0 596 8 10 10 FIL_PAGE_INDEX 0 596 9 11 11 FIL_PAGE_INDEX 0 596 10 12 12 FIL_PAGE_INDEX 0 596 11 13 13 FIL_PAGE_INDEX 0 596 12 14 14 FIL_PAGE_INDEX 0 596 13 15 15 FIL_PAGE_INDEX 0 596 14 18 16 FIL_PAGE_INDEX 0 597 4294967295 17 17 FIL_PAGE_INDEX 0 597 16 4294967295 18 FIL_PAGE_INDEX 0 596 15 19 19 FIL_PAGE_INDEX 0 596 18 20 20 FIL_PAGE_INDEX 0 596 19 4294967295
首先我们观察INDEX_ID，这是索引在InnoDB中的唯一编号，通过输出我们可以看到sakila.film表有4个索引，编号分别为: 596, 597, 598和599，INDEX_ID对应的页存储的就是该索引的数据。我们可以在MySQL中查到对应信息:
selectidx.space space_id,idx.page_no,index_id,idx.name index_name,tab.name table_name
from innodb_indexes idx, innodb_tables tab
whereidx.table_id = tab.table_idand index_id in(596, 597, 598, 599);--语句输出:
space_id|page_no|index_id|index_name |table_name |
--------+-------+--------+---------------------------+-----------+387| 4| 596|PRIMARY |sakila/film|387| 5| 597|idx_title |sakila/film|387| 6| 598|idx_fk_language_id |sakila/film|387| 7| 599|idx_fk_original_language_id|sakila/film|
这与我们解析的结果是一致的。结合PAGE_LEVEL和PAGE_PREV/PAGE_NEXT信息可以得到整棵B-Tree的基本层次结构, 以主键(PRIMARY, 596)为例，我们可以看到596号索引最大的page_level为1，位于page(4)， 最大的level代表着树的根节点(root)， page4的page_next和page_prev都为0xffffffff(4294967295)，可以理解为指向自己或者终结。page(8)的page_prev为0xffffffff，level=0，代表叶节点，是叶节点的最左边节点。page(20)的page_nex为0xffffff, level=0, 说明是叶子节点最右边的节点。所以根据解析输出，我们可以描绘树的基本结构：
Level 1: page(4)|+---------+----------+---------+--------+/ / | \ \
Level 0: page(8) <-> page(9) <-> page(10) <-> ... <-> page(20)
后续文章将开始讨FIL_PAGE_INDEX页内的记录内容。