InnoDB索引与算法
2018-05-29 19:09:53 小德 MySQL 访问次数 574


一、写在前面

    B+tree B  表示平衡,B+树索引不能通过给定键值得具体行,只能找到数据行所在的页,然后把页读入到内存,再内存中进行查找。所有节点按键值大小顺序放入同一层叶子节点上,由各叶子节点指针进行连接。

    B+tree索引可以分为聚集索引和辅助索引,都是B+tree,叶子节点存放所有的数据,辅助索引不同的地方在于,叶子节点存放的不是一整行的信息。

平衡二叉树:平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

查找算法:分治法:二分查找。  

 

二、聚集索引与辅助索引

    clustered index 按照每张表的主键构造一颗B+树,叶子节点存放完整行的记录数据,其叶子节点也成数据页,每个数据页通过双向链表来进行连接;查询优化器倾向聚集索引。因为定义了数据的逻辑顺序,聚集索引能很快访问针对范围的查询。

    辅助索引(secondary index) 叶子节点不包含行记录的全部数据,包含键值和一个书签,书签告诉InnoDB存储引擎找到相对应的行数据。遍历辅助索引获得指向主键索引的主键,然后再通过主键找到完整行记录

    覆盖索引:InnoBD支持覆盖索引,辅助索引不需要通过查询聚集索引即可拿到整行信息,可减少IO操作,对select * count  统计查询很有效


三、B+tree索引的管理

    MySQL创建或删除索引过程:

            创建一个临时表,通过alter table  重新定义表结构;把原有数据导入临时表;删除原表;把临时表命名为原表。===》很慢

    快速创建索引:

            对辅助索引:对创建索引的表加一个S锁,创建过程不需要增加临时表,更新内部视图,并将辅助索引标记为可用,同时删除MySQL数据库内部视图对该表的索引定义

            FaceBook OSC。。

      cardinality 值:性别字段不必建索引 50%;


 三、B+tree索引的使用

        对OLTP一次查询少部分数据要使用,对于OLAP项目,针对统计信息不需要对名字 手机号之类加索引

        联合索引:略

        不使用(辅助)索引的情况:访问数据占比20%左右是,优化器会选择使用聚集索引。


四、哈希索引

        只能用来搜索等值查询,采用链表处理哈希冲突。


五、全文检索    

        B+tree只支持前序查找 Like ‘XXX%’;

        实际需求需要LIke ‘%XXX%’;InnoDB的全文检索使用倒排索引,利用辅助表在单词与单词自身在一个或多个文档中所在位置的映射。

       inverted file index  {单词,单词所在文档ID}  

       full inverted index  {单词,(单词所在文档ID,再具体文档中的位置)}

       倒排索引需要将word放入一个辅助表中,FTS Index Cache  红黑数结构。

    

        参考:《MySQL技术引擎内幕InnoDB存储引擎》 第二版 ---机械工业出版社