一、写在前面

    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存储引擎》 第二版 ---机械工业出版社