InnoDB存储引擎索引概述
InnoDB存储引擎支持以下几种常见的索引:
❑B+树索引
❑全文索引
❑哈希索引
B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存,再在内存中进行查找,最后得到要查找的数据。
B+树是通过二叉查找树,再由平衡二叉树,B树演化而来。
平衡二叉树的定义如下:首先符合二叉查找树的定义,其次必须满足任何节点的两个子树的高度最大差为1。
平衡二叉树的查询速度的确很快,但是维护一棵平衡二叉树的代价是非常大的。通常来说,需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。
对一棵平衡树的维护是有一定开销的,不过平衡二叉树多用于内存结构对象中,因此维护的开销相对较小。
B+树
B+树由B树和索引顺序访问方法(ISAM)演化而来,但是在现实使用过程中几乎已经没有使用B树的情况了。
B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接。其高度为2,每页可存放4条记录,扇出(fan out)为5。
B+索引在数据库中有一个特点是高扇出性,因此在数据库中,B+树的高度一般都在2~4层,这也就是说查找某一键值的行记录时最多只需要2到4次IO,这倒不错。因为当前一般的机械磁盘每秒至少可以做100次IO,2~4次的IO意味着查询时间只需0.02~0.04秒。
聚集索引(clustered index)
聚集索引(clustered index)就是按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据,也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样,每个数据页都通过一个双向链表来进行链接。
聚集索引的存储并不是物理上连续的,而是逻辑上连续的。这其中有两点:一是前面说过的页通过双向链表链接,页按照主键的顺序排序;另一点是每个页中的记录也是通过双向链表进行维护的,物理存储上可以同样不按照主键存储。
聚集索引的另一个好处是,它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。如用户需要查询一张注册用户的表,查询最后注册的10位用户,由于B+树索引是双向链表的,用户可以快速找到最后一个数据页,并取出10条记录。
辅助索引(Secondary Index)
叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外,每个叶子节点中的索引行中还包含了一个书签(bookmark)。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎表是索引组织表,因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。
B+树索引的使用
联合索引
覆盖索引
哈希索引
哈希索引只能用来搜索等值的查询
全文检索
将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息,也可以进行各种统计和分析。
倒排索引(inverted index)
❑inverted file index,其表现形式为 {单词,单词所在文档的ID}
❑full inverted index,其表现形式为 {单词,(单词所在文档的ID,在具体文档中的位置)}
B+树索引 和 哈希索引还比较好理解
光全文索引就可以出一本书咯,目前看概念没法子理解%>_<%