索引是一种让你快速找到数据的数据结构

时间:2022-11-04 14:05:36

人都是有惯性的,对于使用数据库的人来说已经习惯于使用索引,大多数人都只知道我们可以用索引来提高数据访问的性能。对于索引是如何实现这一点的,大家可能也清楚,通过只在叶结点中存储索引数据的B+TREE来快速定位到数据所在的位置,再从表中获得数据就可以实现比全表扫描更快的获得数据的目的了。

索引是一种让你快速找到数据的数据结构

不过随着惯性,我们一直都在把我们的业务模型与B树去做融合,尽可能让我们的应用访问数据的模式更符合B树的结构,从而获得更好的性能。比如说控制不会在索引中出现,那么我们给创建一个(col,1)这样的索引,让索引中也能够包含col的空值记录。比如说我们的索引字段的独立值数很少的时候,会发现使用索引可能还不如全表扫描快,使用位图索引又容易出现并发写入时锁放大的性能问题。如果我们只访问几个占表的记录数中较少的值的时候,我们发现可以用B树索引来提升性能。只不过我们创建的索引包含了对所有数据的索引值对于应用来说是没有任何用途的。

实际上在使用索引的时候,我们已经忘记了使用索引的目的就是为了更快速的找到数据,索引并不是只能是B树或者位图,索引是一种辅助性的数据结构,它其实是可以被定义成任何样式的。比如仅仅是为了解决你的某条SQL中几张表的复杂关联关系,或者仅仅为了某个应用所需要的快速查找数据的需求。你可以自己设计一种最符合应用特点的索引结构,来实现对此类应用的加速。

实际上有一类对表关联查询特别有效的索引,这种索引出现了几十年了,可能我们还从来没有使用过,那就是连接位图索引BMJ。这种索引在OLAP系统中可能用的更多一些,在OLTP系统中,因为会影响DML的性能而很少使用。不过如果你的数据是写入后较少改动的,并且并发写入不存在明显瓶颈的时候,BMJ在OLTP中使用也是安全的。BMJ是一种专门用于表连接的索引,其性能高于一般的HASH JOIN或者NL。

如果你在使用PostgreSQL数据库,那么你会对索引设计感到既兴奋又迷茫。PG数据库的索引类型太丰富了。哪怕我们排除一些用于全文检索,JSON的索引类。我们也能发现很多有趣的索引类型。

比如说我们上面的这个例子,每次我们只是从上亿条数据中找出几百条特殊的数据,那么在PG里就可以使用部分索引(Partial Index),这种索引我们可以看作是一种特殊的函数索引,其存储结构也是B-TREE的。部分索引也称为过滤索引,它只覆盖表数据的一个子集,是一个带有 WHERE 子句的索引。部分索引有助于加快查询速度,同时减少索引的大小,这些索引需要更少的存储空间,它们更易于维护,扫描速度更快。比如在一张表上,STATUS=001的数据是我们要SELECT出来进行处理的,处理后STATUS就变成了002,因此这张表上的STATUS字段值域是倾斜的,001的记录可能只有几百条,而002的记录有上千万条。在PostgreSQL中,我们可以通过Partial索引获得更好的效果。

create index idx_partial_status on t_order (status) where status=’001’;

这个索引中只有status=’001’的数据,因此索引十分小。访问的效率也十分高。再复杂一些,我们可以创建类似这样的PartialIndex。

create index idx_partial_status on t_order (status) where status in (’001’,’002’);

如果我们的where 条件是status in (’001’,’002’),那么这个索引就能够发挥作用了。

另外一种比较有趣的PG索引类型是覆盖索引。在做Oracle数据库 的时候,对于回表数据量较大的查询,如果不回表访问那么可以大大提升性能。这种情况下Oracle有两种方法来解决,一种是创建一个包含所有返回字段的索引,使执行计划变成INDEX ONLY SCAN,从而提升性能。不过如果要返回的字段数量很多,那么这个索引的冗余部分就很多,甚至有时候我们只能使用索引组织表(IOT)来替代索引了。实际上可能在SQL中用于定位数据的出现在WHERE条件中的字段数量并不多,大多数是为了避免回表而增加的额外字段,是不需要排序的。因此PG数据库中出现了一种被称为覆盖索引。覆盖索引(Covering index)是PostgreSQL 11开始引入的一种新的索引。这是一种特殊的复合索引,允许索引中存储附加的非索引字段。比如:

select col1 from tab1 where col2=3;

在没有覆盖索引之前,我们需要创建一个(col2,col1)的复合索引,从而让这条SQL使用Index Only Scan来提高执行效率,减少对表的访问。出现覆盖索引后,可以创建一个(col2) include (col1)的索引。和传统的复合索引不同的是,附加字段不需要参与B-TREE的构建,让索引的效率更高。

实际上在纷繁复杂的应用场景中,PG提供的索引种类可能还无法覆盖一些特殊的场景。不过也不用怕,PG提供了一个十分简单的方法,让你扩展自己的索引类型,从而来解决你应用中很难解决的性能问题。只要你能够想到,索引是一种让你更快找到你所需要的数据的附加数据结构。你可以使用标准的,通用的B树、位图等结构,也可以使用只有你的应用能理解的数据结构来查找到你所需要的数据,因此如果使用的是PG数据库,那么你很幸运,你可以自己去定义一种新的索引来适配你的应用。

也许我在写这篇文章的时候,也有一些其他的数据库也具备了这个能力,如果这样,那就对了,索引本来就是这样的,索引并不是你平时理解的那种死板的数据结构。也并不是你的应用必须去适合B树索引,索引也可以去适应你的应用。希望我们的基于PG开源代码开发的国产数据库,千万要保留这个接口,有时候它真的能救命。