MySQL 技术内幕：InnoDB存储引擎——读书笔记（六）

hfutwhy

    B+树索引并不能找到一个给定键值的具体行，只能找到被查找数据所在的页，然后数据库通过把页读入内存，再在内存中对每页中的Page Directory中的槽（是按照主键的顺序存放的）进行二分查找，最后得到查找的数据。

    平衡二叉树：首先符合二叉查找树的定义（左节点键值<根节点键值 <右节点键值），其次满足任何节点的左右两个子树的高度差最大为1。平衡二叉树对于查询速度很快，但是维护该结构的代价也是非常大的，不过平衡二叉树多用于内存结构对象中，维护开销相对比较小。
    B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各页节点通过双向链表指针进行连接。（下图为一棵高度为2的B+树）

B+树的插入操作

Leaf Page Full	Index Page Full	操作
NO	NO	直接将记录插入叶节点
YES	NO	1.拆分Leaf Page                  2.将中间的节点放入Index Page 3.小于中间节点的记录放入左边    4.大于等于中间节点的记录放入右边
YES	YES	1.拆分Leaf Page                    2.小于中间节点的记录放入左边 3.大于等于中间节点的记录放入右边  4.拆分Index Page 5.小于中间节点的记录放左边        6.大于中间节点的记录放右边 7.中间节点放入上一层Index Page

    页的拆分意味着磁盘的操作，为了减少页拆分对性能的影响，B+树提供了旋转(rotation)。旋转发生在Leaf Page已满、但其左右兄弟节点没有满的情况下，B+树会首先检查是否可以进行旋转操作，将记录移至所在页的兄弟节点上，而不是急于做拆分页。

B+树的删除操作

Leaf Page Below Fill Factor	Index Page Below Fill Factor	操作
NO	NO	直接将记录从叶节点删除，若该节点还是Index Page的节点，则用该节点的右节点代替
YES	NO	合并叶节点及其兄弟节点，同时更新Index Page
YES	YES	1.合并叶节点及其兄弟节点 2.更新Index Page 3.合并Index Page及其兄弟节点

     B+树高度一般在2~3层。根据存储数据的不同，可以分为聚 集索引(Clustered Index)和辅助聚 集索引(Secondary Index)，两者的区别在于：叶节点存放的是否是已整行的信息。

  聚 集索引

    每张表只能拥有一个聚 集索引，聚 集索引的存储并不是物理上的连续，而是逻辑上的连续。对于主键的排序查找和范围查找速度非常快。

  辅助索引

    辅助索引的叶节点不包含行的全部数据，除包含键值外，还包括了一个指向相应行数据的聚 集索引键的书签(bookmark)。在利用辅助索引查找数据时，InnoDB会遍历辅助索引并通过叶节点的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

B+树索引的管理

    通过ALTER TALBE ADD/DROP INDEX或者CREATE/DROP INDEX创建或删除。MySQL对于索引的添加和删除，先创建一张新的临时表，然后将数据导入临时表，之后删除元表，最后把临时表重名为原来的表名。故对于大表，添加或删除索引会耗时很长。

    在InnoDB Plugin中，对于辅助索引的创建，MySQL采用一种快速索引创建的方法：在表上加一个S锁，不需重建表。

    可以通过SHOW INDEX FROM tab_name查看表的索引信息，通过ANALYZE TABLE tab_name更新表的索引统计值。

MySQL查询优化器也是基于成本的，会根据实际情况使用或不使用索引。（当取出的数据量超过表中数据的20%时，优化器便不会使用索引，而是进行全表扫描。作者经验）

    数据库中，顺序读是指根据索引的叶节点数据就能顺序地读取所需要的行数据，只是逻辑地顺序读，在物理磁盘上可能还是随机读取。

    随机读，一般需要根据辅助索引叶节点中的主键寻找实际行数据。而辅助索引和主键所在的数据段不同，因此访问方式是随机的。

    为了提高读取性能，InnoDB采用预读取方式将所需数据读入内存。包括随机预读取（random read ahead）和线性预读取（linear read ahead）。但是自InnoDB Plugin1.0.4起，随机访问的预读取被取消了，保留了线性预读取，并加入了innodb_read_ahead_threshold参数，控制一个区中多少页被顺序访问时，InnoDB才启用预读取，预读取下一个页中所有的页。

    另一个问题：固态硬盘的技术使得随机读取的速度极大提高，但数据产品并没有充分利用到这一点。

哈希算法

        InnoDB使用哈希算法对字典进行查找，其冲突机制采用链表方式，哈希函数采用除法散列方式。对于缓冲池页的哈希表来说，在缓冲池中的Page页都有一个chain指针，它指向哈希函数值的页。

    哈希索引只能用来搜索等值的查询。

注：如若涉及版权或者其他问题，请联系本人。