MySQL索引及存储问题

1 索引简述

MySQL中的索引结构

在MySQL中，使用最多的索引结构是B+树索引，此外还有哈希索引，但很少使用。

哈希表原则上查找更快，但基本不使用，因为哈希表解决不了范围查找，只能等值查询，无法用于排序！

B+树的特点

1）B+树存储时所有非叶节点存储索引，叶节点存储数据。聚集索引的话叶节点存储的是全部数据，非聚集索引只存储主键ID和索引值。

2）INnoDB中最小储存单元是页，默认大小为16KB，而文件系统中最小单元是磁盘块，为4KB。

3）B+树的任务只是通过索引找到对应的数据页，而数据页大小16KB，里面存储了多行数据。

4）B+树索引一个索引页可以存储多少个索引：以bigint建索引的话，一个bigint为8字节，光存索引值还不行，还得存一个指针找到下一个索引页或数据页，InnoDB中指针大小为6个字节。索引result=16*1024/(8+6)=1170。

5）高度为3和高度为4的B+树可以存储多少索引：高度为3的话，索引有两层，第一层只有一个节点，有1170个个索引，第二层有1170个节点，每个节点有1170个索引，第三层为数据页，从而第三层有1170*1170个数据页，每个数据页为16Kb。假设每行数据占用1KB，那么三层B+数据存储1170 * 1170 * 16条数据，大约2000万。

如果高度为4，存的数据行数就非常大了…

为什么是B+树，而不是B树：

1）非叶子结点不存放真正的数据，如此一来数据页能放更多的索引值，每个节点的索引范围更大，i/o次数相应更少；

2）所有叶子结点按照顺序链表存储，增大区间查找效率！！

2 储存格式

B+树负责找到对应的数据页，那一个数据页当中的存储是怎样的？

在结构中，Header就是记录文件或页相关的状态信息等，真正关心的是每一行数据如何存放，怎么定位到具体的行。

真正的行数据记录在UserRecords中，通过链表的形式串起来，我们知道链表的遍历时线性遍历，效率低下，所以在InnoDB的数据页中，有一个Page Directory页目录存放记录的相对位置，页目录由多个slot（槽）组成，每个槽可能指向多个行记录，即稀疏目录。

当我们查找某一行数据时，先通过Page Directory进行二分查找找到对应的slot，再遍历slot中的数据找到对应的行记录。