B+树索引(1)简易版本索引 --mysql从入门到精通（十三)

前面我们说了innoDB有很多页类型，主要介绍了index索引页，包含七个主要部分。File header里有效验和和file_page_prev和file_page_next吧所有的页联系起来，组成双向链表。Page header里有当前页的槽点和记录数，还有next record来吧每个数据连接起来，组成单链表。查询的时候有page directory。File trailer里的效验和能检验数据是否完成。如果上面说的这些你都不明白，建议吧前面的文章再看一看，接下来的知识不适合你。什么？前面内容太多，太生涩看不懂？好的，等我！

InnoDB(7)数据持久化 --mysql从入门到精通（十二)

没有索引的情况下查找

回忆一下，如果查询主键，则会用二分查找法找到对应的槽，然后遍历该槽的记录，找到对应的数据。

如果是非主键其他列查询，因为数据页中并没有非主键页的页目录，所以无法通过二分查找法定位槽，这种情况下，只能从最小记录，依次遍历页里单链表的每条数据。

上诉是主键查找的时候，会用二分查找法找到页中对应的槽，其实不管属于不属于主键查找，找页都是在双向链表一个个遍历的，所以只能从第一个慢慢往后找，定位到字节需要的页，如果数据有上亿，这种是非常耗时的，mysql的设计者肯定不允许这种事情发生，这时候我们的索引就闪亮登场！！！

索引

先创建一个index_tb表，指定行格式为compcat，设置主键为c1，两个int类型，一个char类型c3：

mysql> create TABLE index_tb(
    -> c1 int,
    -> c2 int,
    -> c3 char(1),
    -> primary key(c1)
    -> 
    -> )row_format=Compact;
Query OK, 0 rows affected (0.04 sec)
 
 
//插入一些数据
mysql> INSERT INTO index_tb VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)

那我们现在表里面的数据结构就是：

record_type:记录头信息里的一项属性，表示当前记录的类型，0表示普通数据，2表示最小记录，3表示最大记录，1我们还没用到过,马上就要用到了。

next_record:记录头信息里的，下一条地址对本条地址的偏移量，方便找到下一条数据。

各个列的值：c1,c2,c3。

其他信息：记录真实数据的额外信息(null值列表，变长字段长度列表，头部信息)，和其他隐藏列的值(最小隐藏列和最大隐藏列)。

一个简易版本索引

前面我们知道为了在页中快速查询数据在某个槽点中，我们有了目录page directory的概念方便我们快速查到数据，那我们查找数据在某个页时候，怎么找呢，也可以通过页目录来找到对应的页，但想通过目录查找，必须满足一些规则才可以 ，比如槽里的数据，会按主键从小到大排序，那我们页目录查找页必须满足：

1、下一个数据页中的主键必须大于上一个数据页中的主键。

前面我们已经insert了不少数据，为了我们演示，我们假设一个数据页只能存放三条数据(实际一个数据页能存放大量的数据)。

此刻我们的数据显示，record_type类型分别为：

页10：2，0，0，0，3

三个0的数据分别存储着：1，4，u；3，9，d；5，3，y。

当我们再插入一条数据，则在另一个页:

 mysql>  INSERT INTO index_tb VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)

页30：2，0，3

0的数据存储着：4,4,a。

页10 和页30是正常的，因为页的分配并不是连续的，因为5>4，但为了满足条件，所以他插入的时候，会有两个步骤，第一步将主键为5的移动到页30，第二步将主键为4移动到页10。

所以在插入数据的时候，必须保证下一个页的主键必须大于上一个页的主键而做一些操作，这个过程叫做’页分裂‘。

当我们有多个页的时候，这时候如何找到页，我们要给页做一个目录，key和page_no，

key：页里的最小主键值(1，5)。

page_no：页的名称(页10，页30)。

所以我们查找的时候，1、先根据二分查找法，确定主键的值在哪个key的页目录中。

2、在找到key值对应的page_no页，去页中找到具体值。

而这个key和page_no组成的目录就叫做索引。