不背八股文：最简单的索引原理

索引是对数据库表中一列或多列的值进行排序的一种数据结构，使用索引可以快速访问数据库表中的特定信息。

索引的作用就相当于书的目录。打个比方: 我们在查字典的时候，如果没有目录，那我们就只能一页一页的去找我们需要查的那个字，速度很慢。如果有目录了，我们只需要先去目录里查找字的位置，然后直接翻到那一页就行了。索引底层数据结构存在很多种类型，常见的索引结构有: B 树， B+树 和 Hash、红黑树。在 MySQL 中，无论是 Innodb 还是 MyIsam，都使用了 B+树作为索引结构。

大家对上面这段描述索引的概念应该都很熟悉，但是看完后总有种好像看了又好像什么都没看的感觉， 就好像是领导讲话，说了很多话但好像又什么都没说。 所以我们试图用最简洁易懂的方式，不背八股文，用最简单的方式说明索引原理。

索引的目的

为了提高查询的效率。因为在基于行存储的数据库中查询会扫描更多的磁盘，基于这种存储结构查询性能受到天然的限制。

索引的本质

一张更小的表或者说是一块更小的磁盘空间，这个大小是和行数据所对比的。

模拟索引

create table `user` (
    id bigint not null primary key ,
    firstname varchar(30) not null ,
    lastname varchar(30) not null ,
    age tinyint unsigned not null 
) ;

在 user 表中创建 firstname , lastname 的组合索引，我们通过自己建表的方式实现。

create table `user_idx_firstname_lastname` (
    id bigint not null ,
    firstname varchar(30) not null ,
    lastname varchar(30) not null
) ;

我们直接执行这条 SQL 会直接去查行空间，行空间比索引空间大，检索起来较慢。

select * from user where firstname = 'Smith' and lastname = 'Joe' ;

先查索引:

select id from user_idx_firstname_lastname where firstname = 'Smith' and lastname = 'Joe' ;

先在索引空间上检索，找到目标行的行id,再用行 id 去行空间检索，就减少了检索的范围。

不同类型的索引

有不同特质的数据结构存储索引数据，核心思想不变。

BTree

B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。 特性可以排序。

HASH

对索引数据进行 hash 加工，无法排序，能快速查找。

BITMAP

bitmap索引就是用位图表示的索引，对列的每个键值建立一个位图。所以相对于b-tree索引，占用的存储空间非常小，创建和使用非常快。缺点是修改操作锁粒度大，不适合频繁更新。

位图索引是一种针对多个字段的简单查询设计一种特殊的索引，适用范围比较小，只适用于字段值固定并且值的种类很少的情况，比如性别，只有男和女，或者级别，状态等等，并且只有在同时对多个这样的字段查询时才能体现出位图的优势。 位图的基本思想就是对每一个条件都用0或者1来表示，如有5条记录，性别分别是男，女，男，男，女，那么如果使用位图索引就会建立两个位图，对应男的10110和对应女的01001,这样做有什么好处呢，就是如果同时对多个这种类型的字段进行and或or查询时，可以使用按位与和按位或来直接得到结果了。

如下图，bitmap索引将每个被索引的列的值作为KEY，使用每个BIT表示一行，当这行中包含这个值时，设置为1，否则设置为0。

该文章同步在微信公众号：【DevXTalk】

原文链接