精华内容
下载资源
问答
  • MySQL Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。...
  • 深入解析了Mysql的B+Tree索引底层数据结构,以及MyISAM和InnoDB 存储引擎的索引底层原理。

    深入解析了Mysql的B+Tree索引底层数据结构,以及MyISAM和InnoDB 存储引擎的索引底层原理。

    上一篇文章中,我们介绍了索引的概念以及MySQL常见索引类型:索引的概念以及MySQL七种索引类型。下面我们来看看常见的索引结构的底层实现原理。包括B-Tree、B+Tree的数据结构,以及MyISAM和InnoDB 存储引擎对于B+Tree索引的具体实现。

    1 索引的数据结构

    索引有多种数据结构,在MySQL中,索引是在存储引擎层而不是服务器层实现的。所以,并没有统一的索引标准:不同存储引擎的索引的工作方式不一样,也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一类型的索引,其底层实现也可能不同。

    一般来说常见的索引结构是HASH和BTREE
    在这里插入图片描述

    2 B-Tree索引的介绍

    如果在谈论索引的时候没有指明类型,那么多半说的是B-Tree索引,它使用B-Tree数据结构来存储数据,大多数存储引擎都支持这种索引。

    不过,虽然大多都支持B-Tree索引,但是底层的存储引擎也可能使用不同的存储结构,例如NDB集群存储引擎内部实际上使用了T-Tree结构存储这种索引,即使其名字是BTREE;而InnoDB和MyISAM则使用的是B+Tree结构(实际上很多存储引擎使用的是B+Tree,即每个叶子节点都包含指向下一个叶子节点的指针,从而方便叶子节点的范围遍历),但其名字也还是叫BTREE

    我们通常所说聚集索引、覆盖索引、组合索引、前缀索引、普通索引、唯一索引等,没有特别说明,默认都是使用B+Tree结构的索引

    2.1 为什么选择B-Tree结构

    B-Tree是一种自平衡的多路查找树,其中B是Balanced (平衡)的意思,节点最大的孩子数目称为B-Tree的阶(order)。

    关于B-Tree和B+Tree,可以看看以前我的这篇文章:数据结构—多路查找树中的2-3树、2-3-4树、B树、B+树的原理详解,里面有更加详细的介绍,下面的内容都是总结自这篇文章。

    B-Tree节点也是天然有序的(排序),和平衡二叉树一样,B-Tree也能以O(logn)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构,并且所有的叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。

    不同的是,平衡二叉树是一般是用于优化内存中的数据的查找速度的数据结构,B-Tree一般用于优化外存中数据的查找数据的数据结构,普遍运用在数据库索引结构和文件系统。

    对硬盘中的数据结构的某个节点的访问就会发起一次磁盘IO请求,IO操作耗时远大于内存中操作的耗时。如果一棵B-Tree的阶为1001(即1个节点包含1000个关键字),高度为2,它可以储存超过10亿个关键字。那么在这棵树上,寻找某一个关键字至多需要两次硬盘的读取即可。如果采用二叉树来存储这10亿个关键字,那么会需要非常多次数的IO请求。虽然两种数据结构最终找到某个数据所需的比较次数不会少,但是使用B-Tree时,可以经历非常少的IO次数(将一大批数据IO到内存中进行比较),而IO操作时非常耗时的。

    由于B-Tree每个节点能包含比二叉树更多的数据,同时树的层级比原来的二叉树更少的特性,加上数据库充分利用了磁盘预读原理(磁盘数据存储是采用块的形式存储的,每个块的大小为4k或8k,每次IO进行数据读取时,同一个磁盘块的数据可以一次性读取出来(InnoDB存储引擎一次IO会读取的一页(默认一页16K))),因此采用B-Tree作为索引结构,能够减少定位记录时所经历IO次数,从而加快存取速度。可以说,B-Tree的数据结构就是为内外存的数据交互准备的。

    以上特点也是“为什么不选择红黑树或者其他二叉树作为外存中进行查找的数据结构”等问题的原因。

    2.2 B+Tree和B-Tree结构的区别

    B+Tree可以说是B-Tree的升级版,相对于B-Tree来说B+Tree更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。

    目前大部分数据库系统及文件系统都采用 B-Tree或其变种B+Tree作为索引结构。

    B-Tree和B+Tree的主要区别在于:

    1. B-Tree的非叶节点会存储关键字(key)及其对应的数据(data),而B+Tree的非叶节点只存关键字索引(key),不会存具体的数据(data),因此B+Tree的一个节点相比B-Tree能存储更多的索引元素,一次性读入内存的需要查找的关键字(key)也就越多,存储同样的数量的数据,B+Tree的高度可以更小,相对IO读写次数就降低了。
    2. B-Tree的查询效率并不稳定,最好的情况只查询一次(根节点),最坏情况是查找到叶子节点,而B+Tree由于非叶节点不存数据,而只是叶子节点中存储有关键字的索引。所有查询都要查找到叶子节点才算命中,查询效率比较稳定。这对于sql语句的优化是非常有帮助的。
    3. B-Tree的叶子节点之间都是独立的,而B+Tree所有叶子节点形成有序链表(可以是双向链表),只需要去遍历叶子节点就可以实现整棵树的遍历。提高范围查找的效率,而B-Tree不支持这样的操作或者说效率太低。

    如下,是一颗典型的B-Tree,它的非叶节点中存储了key和data:
    在这里插入图片描述

    如下,是一颗mysql索引表中实现的一种B+Tree,它的非叶节点中只存储了key,叶子节点之间使用链表关联起来:
    在这里插入图片描述

    这里的data,不同的存储引擎有不同的实现,对于MyISAM来说,data域存放的是数据记录的地址,对于InnoDB来说,data域保存了完整的数据记录。另外,即使InnoDB和MyISAM的BTREE索引都是采用的B+Tree结构,但其具体的存储实现上,仍有很大的不同。

    磁盘中的数据页是按顺序一页一页存放的,读取的时候也都是以页为单位读取的,InnoDB引擎一页的大小通常为16K。而B+Tree结构的每一页的数据还会从按照从小到大的顺序进行排序。

    B+Tree索引结构中,非叶节点作为索引页,key专门存放索引值,data域存储的是指向另一页的指针,key索引值的大小就是data对应的页的数据中的最小索引值,即对应页最左边的数据。

    叶节点作为数据叶,key同样是索引,但data存放了对应的数据,这个数据可能是主键id,指向表数据的指针,或者是真实的表数据,两两相邻的数据页之间会采用双向链表的格式互相引用,而每一页中的数据之间则是通过单链表来连接的。

    3 MyISAM的BTREE索引实现

    MyISAM存储引擎的数据文件和索引文件是分开存储的,索引文件名为tablename. MYI,而数据文件名为tablename.MDB,并且表空间中可存储行记录数。

    在MyISAM引擎中,使用 B+Tree作为BTREE索引结构,叶节点的关键key是索引列的值,而data 则是保存数据记录的地址。

    假设有一个user表,具有id、age、name字段,其中id是主键。下图是 在MyISAM 引擎中user表的主键索引图:
    在这里插入图片描述

    假设我们要根据主键id精确查询值为12的数据,则需要进行4次磁盘IO,其中3次索引IO,一次数据IO。

    假设我们要根据主键id精确查询值为10~20的数据,则需要进行5次磁盘IO,其中4次索引IO,一次数据IO。多出来的一次索引IO是对叶子节点横向进行的范围查找,并且id的查询范围跨越了不同的数据块,如果范围在同一个数据块中,则不需要多一次的范围查找。

    MyISAM存储引擎的主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。所以在查询时即使是等值查询,也需要按照范围查询的方式在辅助索引树中检索数据。

    对于user表,假设age字段是辅助索引,那么下图是 MyISAM 引擎中user表的辅助索引图:
    在这里插入图片描述

    另外,加载到内存中的数据将可能被MyISAM缓存起来,因此不是每次的查找都会进行磁盘IO。

    4 InnoDB的BTREE索引实现

    InnoDB 也使用 B+Tree 作为BTREE索引结构。一个 InnoDB 表包含两部分,即:表结构定义和数据。在 MySQL 8.0 版本以前,表结构是存在以.frm 为后缀的文件里。而 MySQL 8.0 版本,则已经允许把表结构定义放在系统数据表中了。因为表结构定义占用的空间很小。

    MyISAM 索引文件和数据文件是分离的,索引文件仅保存数据记录的地址,而InnoDB的数据文件本身就是索引文件,数据和索引存储在一个文件t_tablename.ibd中。

    其表数据文件本身就是按 B+Tree 组织的一个索引结构,树的叶节点 data 域保存了完整的数据记录,InnoDB表数据文件本身就是主索引,索引的key是数据表的主键,这种索引就是主键索引,也称为聚集(聚簇)索引,相应的,MyISAM存储引擎的索引被称为非聚集(聚簇)索引。

    聚簇索引的一个叶子节点存储的是被查找的数据行所在的一个页(同理一个非叶子节点则是存放的一个索引页),通过B+Tree最终找到的也是一个数据页,然后数据库通过把数据页读入内存,再在内存中进行查找(数据是有序的),最后得到要查找的数据。数据页占用固定大小的空间,但是却不一定会被数据填满,因为各种原因,比如,对一个满页插入数据时会使用页分裂计数将一页分裂成两个页,造成每一个数据页有近50%的空闲空间,形成很多磁盘碎片,可能导致全表扫描变慢(数据页和索引页都有可能页分裂)。

    假设有一个user表,具有id、age、name字段,其中id是主键。下图是在InnoDB引擎中user表的主键索引图:
    在这里插入图片描述

    假设我们要根据主键id精确查询值为12的数据,则需要进行3次磁盘IO,其中3次索引IO。

    假设我们要根据主键id精确查询值为10~20的数据,则需要进行4次磁盘IO,其中4次索引IO。多出来的一次索引IO是对叶子节点横向进行的范围查找,并且id的查询范围跨越了不同的数据块,如果范围在同一个数据块中,则不需要多一次的范围查找。

    因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列(唯一索引且not null)作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含ROWID字段作为主键,这个字段长度为6个字节,类型为长整形。

    InnoDB存储引擎除了主键/聚簇索引之外的其余的索引都作为辅助索引,也称为二级索引,或者非聚集(聚簇)索引。需要注意的是,辅助索引的 data 域存储相应记录主键的值而不是地址,而MyISAM的辅助索引的data域同样存放的是数据的地址。

    假设user表的age字段作为辅助索引,下图是在InnoDB引擎中user表的辅助索引图:
    在这里插入图片描述

    在根据主索引(主键)搜索时,直接找到 key 所在的节点的data即可取出数据,而在根据辅助索引查找时,则需要先走辅助索引取出对应的主键值,然后再走一遍主索引。

    根据在辅助索引树中先获取的主键id,然后再到主键索引树检索数据的过程(即二次查询)称为回表查询。假设我们要根据age字段查询age值为18的数据,则需要进行6次磁盘IO,其中3次辅助索引IO,3次回表主索引的IO。我们在应用中应该尽量使用主键查询。

    因此,在设计表的时候,不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。也不建议使用非单调的字段作为主键,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整树的平衡,导致效率降低,而使用自增或者单调字段作为主键则是一个很好的选择(这一点对于MyISAM同样有效)。

    4.1 ROWID

    InnoDB主键策略:每个InnoDB引擎的表必须有一个“聚簇索引”,通常是通过主键索引字段构建。如果没有指定主键,则会通过第一个not null的唯一索引字段构建,如果这两个都没有,那么InnoDB会给你创建一个不可见的,长度为6个字节的row_id字段来构建。(https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html)。

    InnoDB维护了一个全局的dict_sys.row_id值,所有无主键并且没有not null的唯一键的InnoDB表,每插入一行数据,都将当前的dict_sys.row_id值作为要插入数据的row_id,然后把dict_sys.row_id的值加1。

    实际上,在代码实现时row_id是一个长度为8字节的无符号长整型(bigint unsigned)。但是,InnoDB在设计时,给row_id留的只是6个字节的长度,这样写到数据表中时只放了最后6个字节,所以row_id能写到数据表中的值,就有两个特征:

    1. row_id写入表中的值范围,是从0到2^48-1;
    2. 当row_id为2^48-1时,如果再有插入数据的行为要来申请row_id,拿到以后再取最后6个字节的话就是0。

    也就是说,写入表的row_id是从0开始到2^48-1。达到上限后,下一个值就是0,然后继续循环。

    在InnoDB逻辑里,申请到row_id=N后,就将这行数据写入表中;如果表中已经存在row_id=N的行,新写入的行就会覆盖原有的行。

    实际上,InnoDB 存储引擎为每行数据添加了三个 隐藏字段:

    1. DB_TRX_ID(6字节):表示最后一次插入或更新该行的事务 id。此外,delete 操作在内部被视为更新,只不过会在记录头Record header 中的 deleted_flag 字段将其标记为已删除。
    2. DB_ROLL_PTR(7字节) 回滚指针,指向该行的 undo log 。如果该行未被更新,则为空。
    3. DB_ROW_ID(6字节):如果没有设置主键且该表没有唯一非空索引时,InnoDB 会使用该 id
      来生成聚簇索引,这个字段值在所有的表中唯一。

    5 B-Tree索引的有效查询类型

    所谓有效查询类型,就是说发生了如下情况时,可以使用索引扫描查询,而不是全表扫描。

    1. 全值匹配:全值匹配指的是和索引列中的所有列进行匹配,例如查询name为“张三”的用户,此时就是全值匹配,对于多列索引来说,就是所有的索引列都完全匹配。
    2. 匹配最左前缀:对于多列索引可以从右向左一次匹配,后面会想详细讲解最左前缀。
    3. 匹配列前缀:可以只匹配某一列的值的开头部分,例如查询所有姓“张”的用户。对于多列索引,则只能对最左列使用列前缀匹配。
    4. 匹配范围值:由于B-Tree的有序性,可以进行基于索引列的范围匹配。所以索引可以按照升序或者降序进行扫描,以满足精确符合列顺序的ORDER BY、GROUP BY 和DISTINCT等之句的查询需求。
    5. 精确匹配和范围匹配:对于多列索引,可以对左边的列进行精准匹配,对右边的列进行范围匹配。但对于范围匹配之后的列则不能走索引,后面会详细讲解。
    6. 只访问索引的查询:B-Tree通常支持“只访问索引的查询”,即查询只需要访问索引,比如姓名列就是索引列,此时查询所有姓“张”的用户的姓名,那么我们无序访问数据行,因为索引就包含所要返回的全部结果,这是一种“覆盖索引”的优化,避免回表。

    基于这些有效查询类型,后面我们讲到索引优化部分的时候会非常有用。

    参考资料:

    1. 《 MySQL 技术内幕: InnoDB 存储引擎》
    2. 《高性能 MySQL》

    如有需要交流,或者文章有误,请直接留言。另外希望点赞、收藏、关注,我将不间断更新各种Java学习博客!

    展开全文
  • 索引: 语法: CREATE INDEX test1_id_index ON test1 (id); 索引的名字test1_id_index可以自由选择,但我们最好选择一个能让我们想起该索引用途的名字。 为了移除一个索引,可以使用DROP INDEX命令。索引可以随时...

    索引

    语法:

    CREATE INDEX test1_id_index ON test1 (id);
    

    索引的名字test1_id_index可以自由选择,但我们最好选择一个能让我们想起该索引用途的名字。

    为了移除一个索引,可以使用DROP INDEX命令。索引可以随时被创建或删除。

    在一个大表上创建一个索引会耗费很长的时间。默认情况下,PostgreSQL允许在索引创建时并行地进行读(SELECT命令),但写(INSERT、UPDATE和DELETE)则会被阻塞直到索引创建完成。在生产环境中这通常是不可接受的。在创建索引时允许并行的写是可能的, PostgreSQL支持构建索引时不阻塞写入。这种方法通过 指定CREATE INDEX的CONCURRENTLY选项 实现。

    一个索引被创建后,系统必须保持它与表同步。这增加了数据操作的负担。因此哪些很少或从不在查询中使用的索引应该被移除。


    索引类型

    PostgreSQL提供了多种索引类型: B-tree、Hash、GiST、SP-GiST 、GIN 和 BRIN。每一种索引类型使用了 一种不同的算法来适应不同类型的查询。默认情况下, CREATE INDEX命令创建适合于大部分情况的B-tree 索引。
    B-tree索引

    支持的操作符:

    <
    <=
    =
    >=
    >
    BETWEEN
    IN
    IS NULL
    IS NOT NULL
    LIKE (字符开头)
    ILIKE(非字母字符开头)
    

    Hash索引
    Hash索引只能处理简单等值比较。不论何时当一个索引列涉及到一个使用了=操作符的比较时,查询规划器将考虑使用一个Hash索引。下面的命令将创建一个Hash索引:

    CREATE INDEX name ON table USING HASH (column);
    

    GiST索引
    GiST表示通用搜索树。它是一种平衡的树结构的访问方法,它作为一种模板可用来实现任意索引模式。B 树、R 树和很多其他索引模式都可以在GiST中实现。
    GiST索引并不是一种单独的索引,而是可以用于实现很多不同索引策略的基础设施。(需要安装扩展 create extension btree_gist;)
    多用于支持二维几何数据类型的索引化查询
    支持的操作符:

    在这里插入图片描述

    GiST索引也有能力优化“最近邻”搜索,例如:

    SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
    

    它将找到离给定目标点最近的10个位置。能够支持这种查询的能力同样取决于被使用的特定操作符类

    与Btree索引比较的优缺点:

    优点:

    Gist索引适用于多维数据类型和集合数据类型,和Btree索引类似,同样适用于其他的数据类型。和Btree索引相比,Gist多字段索引在查询条件中包含索引字段的任何子集都会使用索引扫描。

    缺点:

    Gist索引创建耗时较长,占用空间也比较大。

    SP-GiST索引
    和GiST相似,SP-GiST索引为支持多种搜索提供了一种基础结构。SP-GiST 允许实现众多不同的非平衡的基于磁盘的数据结构,例如四叉树、k-d树和radix树。
    支持的操作符:
    在这里插入图片描述
    GIN 索引
    GIN意思是通用倒排索引。GIN被设计为处理被索引项为组合值的情况,并且这种索引所处理的查询需要搜索出现在组合项中的元素值。例如,项可以是文档,并且查询可以是搜索包含指定词的文档。

    我们使用词项来表示要被索引的一个组合值,并且用词键来表示一个元素值。GIN总是存储和搜索键,而不是项值本身。

    一个GIN存储一个(键,位置列表)对的集合,这里一个posting list是键在其中出现的一个行 ID 的集合。相同的行 ID 可以出现在多个位置列表中,因为一个项可以包含多于一个键。每个键值只被存储一次,因此对于同一个键出现多次的情况,一个GIN索引是非常紧凑的。

    支持的操作符:
    在这里插入图片描述
    BRIN 索引
    BRIN表示块范围索引。 BRIN是为处理这样的表而设计的:表的规模非常大,并且其中某些列与它们在表中的物理位置存在某种自然关联。一个块范围是一组在表中物理上相邻的页面,对于每一个块范围在 索引中存储了一些摘要信息。例如,一个存储商店销售订单的表可能有一个日期 列记录每个订单产生的时间,并且很多时候较早的订单项也将出现在表中较早的 地方。一个存储 ZIP 代码列的表中一个城市的所有代码可能自然地聚在一起。

    如果索引中存储的摘要信息与查询条件一致,BRIN 索引可以通过常规的位图索引扫描满足查询,并且将会返回每个范围中所有页面 中的所有元组。查询执行器负责再次检查这些元组并且抛弃掉那些不匹配查询条 件的元组 — 换句话说,这些索引是有损的。由于一个BRIN 索引很小,扫描这种索引虽然比使用顺序扫描多出了一点点开销,但是可能会避 免扫描表中很多已知不包含匹配元组的部分。

    一个BRIN索引将存储的特定数据以及该索引将能 满足的特定查询,都依赖于为该索引的每一列所选择的操作符类。具有一种 线性排序顺序的数据类型的操作符类可以存储在每个块范围内的最小和最大 值,例如几何类型可能会存储在块范围内的所有对象的外包盒。

    块范围的尺寸在索引创建时由pages_per_range存储参数决定。 索引项的数量将等于该关系的尺寸(以页面计)除以为 pages_per_range选择的值。因此,该值越小,索引会变得越大 (因为需要存储更多索引项),但是与此同时存储的摘要数据可以更加精确并 且在索引扫描期间可以跳过更多数据块。
    支持的操作符:
    在这里插入图片描述


    多列索引

    一个索引可以定义在表的多个列上。例如,我们有这样一个表:

    CREATE TABLE test2 (
      major int,
      minor int,
      name varchar
    );
    

    (即将我们的/dev目录保存在数据库中)而且我们经常会做如下形式的查询:

    SELECT name FROM test2 WHERE major = constant AND minor = constant;
    

    那么我们可以在major和minor上定义一个索引:

    CREATE INDEX test2_mm_idx ON test2 (major, minor);
    

    目前,只有 B-tree、GiST、GIN 和 BRIN 索引类型支持多列索引,最多可以指定32个列(该限制可以在源代码文件pg_config_manual.h中修改,但是修改后需要重新编译PostgreSQL)。

    一个B-tree索引可以用于条件中涉及到任意索引列子集的查询,但是当先导列(即最左边的那些列)上有约束条件时索引最为有效。确切的规则是:在先导列上的等值约束,加上第一个无等值约束的列上的不等值约束,将被用于限制索引被扫描的部分。在这些列右边的列上的约束将在索引中被检查,这样它们适当节约了对表的访问,但它们并未减小索引被扫描的部分。例如,在(a, b, c)上有一个索引并且给定一个查询条件WHERE a = 5 AND b >= 42 AND c < 77,对索引的扫描将从第一个具有a = 5和b = 42的项开始向上进行,直到最后一个具有a = 5的项。在扫描过程中,具有c >= 77的索引项将被跳过,但是它们还是会被扫描到。这个索引在原则上可以被用于在b和/或c上有约束而在a上没有约束的查询,但是整个索引都不得不被扫描,因此在大部分情况下规划器宁可使用一个顺序的表扫描来替代索引。

    一个多列GiST索引可以用于条件中涉及到任意索引列子集的查询。在其余列上的条件将限制由索引返回的项,但是第一列上的条件是决定索引上扫描量的最重要因素。当第一列中具有很少的可区分值时,一个GiST索引将会相对比较低效,即便在其他列上有很多可区分值。

    一个GIN索引可以用于条件中涉及到任意索引列子集的查询。与B-tree和GiST不同,GIN的搜索效率与查询条件中使用哪些索引列无关。

    多列 BRIN 索引可以被用于涉及该索引被索引列的任意子集的查询条件。和 GIN 相似且不同于 B-树 或者 GiST,索引搜索效率与查询条件使用哪个索引列无关。在单个表上使用多个 BRIN 索引来取代一个多列 BRIN 索引的唯一原因是为了使用不同的pages_per_range存储参数。

    当然,要使索引起作用,查询条件中的列必须要使用适合于索引类型的操作符,使用其他操作符的子句将不会被考虑使用索引。

    多列索引应该较少地使用。在绝大多数情况下,单列索引就足够了且能节约时间和空间。具有超过三个列的索引不太有用,除非该表的使用是极端程式化的。


    索引和ORDER BY

    除了简单地查找查询要返回的行外,一个索引可能还需要将它们以指定的顺序传递。这使得查询中的ORDER BY不需要独立的排序步骤。在PostgreSQL当前支持的索引类型中,只有B-tree可以产生排序后的输出,其他索引类型会把行以一种没有指定的且与实现相关的顺序返回。

    规划器会考虑以两种方式来满足一个ORDER BY说明:扫描一个符合说明的可用索引,或者先以物理顺序扫描表然后再显式排序。对于一个需要扫描表的大部分的查询,一个显式的排序很可能比使用一个索引更快,因为其顺序访问模式使得它所需要的磁盘I/O更少。只有在少数行需要被取出时,索引才会更有用。一种重要的特殊情况是ORDER BY与LIMIT n联合使用:一个显式的排序将会处理所有的数据来确定最前面的n行,但如果有一个符合ORDER BY的索引,前n行将会被直接获取且根本不需要扫描剩下的数据。

    默认情况下,B-tree索引将它的项以升序方式存储,并将空值放在最后(表TID被处理为其它相等条目之间的分线器列)。这意味着对列x上索引的一次前向扫描将产生满足ORDER BY x(或者更长的形式:ORDER BY x ASC NULLS LAST)的结果。索引也可以被后向扫描,产生满足ORDER BY x DESC(ORDER BY x DESC NULLS FIRST, NULLS FIRST是ORDER BY DESC的默认情况)。

    我们可以在创建B-tree索引时通过ASC、DESC、NULLS FIRST和NULLS LAST选项来改变索引的排序,例如:

    CREATE INDEX test2_info_nulls_low ON test2 (info NULLS FIRST);
    CREATE INDEX test3_desc_index ON test3 (id DESC NULLS LAST);
    

    一个以升序存储且将空值前置的索引可以根据扫描方向来支持ORDER BY x ASC NULLS FIRST或 ORDER BY x DESC NULLS LAST。


    唯一索引

    索引也可以被用来强制列值的唯一性,或者是多个列组合值的唯一性。

    CREATE UNIQUE INDEX name ON table (column [, ...]);
    

    当前,只有B-tree能够被声明为唯一。

    当一个索引被声明为唯一时,索引中不允许多个表行具有相同的索引值。空值被视为不相同。一个多列唯一索引将会拒绝在所有索引列上具有相同组合值的表行。

    PostgreSQL会自动为定义了一个唯一约束或主键的表创建一个唯一索引。该索引包含组成主键或唯一约束的所有列(可能是一个多列索引),它也是用于强制这些约束的机制。
    注意
    不需要手工在唯一列上创建索引,如果那样做也只是重复了自动创建的索引而已。


    表达式索引

    一个索引列并不一定是底层表的一个列,也可以是从表的一列或多列计算而来的一个函数或者标量表达式。这种特性对于根据计算结果快速获取表中内容是有用的。

    例如,一种进行大小写不敏感比较的常用方法是使用lower函数:

    SELECT * FROM test1 WHERE lower(col1) = 'value';
    

    这种查询可以利用一个建立在lower(col1)函数结果之上的索引:

    CREATE INDEX test1_lower_col1_idx ON test1 (lower(col1));
    

    表达式索引还允许控制唯一索引的范围。例如,此唯一索引可防止在double precision类型列中存储重复的整数值:

    CREATE UNIQUE INDEX test1_uniq_int ON tests ((floor(double_col)))
    

    如果我们将该索引声明为UNIQUE,它将阻止创建在col1值上只有大小写不同的行。

    另外一个例子,如果我们经常进行如下的查询:

    SELECT * FROM people WHERE (first_name || ' ' || last_name) = 'John Smith';
    

    那么值得创建一个这样的索引:

    CREATE INDEX people_names ON people ((first_name || ' ' || last_name));
    

    正如第二个例子所示,CREATE INDEX命令的语法通常要求在被索引的表达式周围书写圆括号。而如第一个例子所示,当表达式只是一个函数调用时可以省略掉圆括号。

    索引表达式的维护代价较为昂贵,因为在每一个行被插入或更新时都得为它重新计算相应的表达式。然而,索引表达式在进行索引搜索时却不需要重新计算,因为它们的结果已经被存储在索引中了。在上面两个例子中,系统将会发现查询的条件是WHERE indexedcolumn = ‘constant’,因此查询的速度将等同于其他简单索引查询。因此,表达式索引对于检索速度远比插入和更新速度重要的情况非常有用。


    部分索引

    一个部分索引是建立在表的一个子集上,而该子集则由一个条件表达式(被称为部分索引的谓词)定义。而索引中只包含那些符合该谓词的表行的项。部分索引是一种专门的特性,但在很多种情况下它们也很有用。

    使用部分索引的一个主要原因是避免索引公值。由于搜索一个公值的查询(一个在所有表行中占比超过一定百分比的值)不会使用索引,所以完全没有理由将这些行保留在索引中。这可以减小索引的尺寸,同时也将加速使用索引的查询。它也将加速很多表更新操作,因为这种索引并不需要在所有情况下都被更新。

    如果我们有一个表包含已上账和未上账的订单,其中未上账的订单在整个表中占据一小部分且它们是最经常被访问的行。我们可以通过只在未上账的行上创建一个索引来提高性能。创建索引的命令如下:

    CREATE INDEX orders_unbilled_index ON orders (order_nr)
        WHERE billed is not true;
    

    使用该索引的一个可能查询是:

    SELECT * FROM orders WHERE billed is not true AND order_nr < 10000;
    

    然而,索引也可以用于完全不涉及order_nr的查询,例如:

    SELECT * FROM orders WHERE billed is not true AND amount > 5000.00;
    

    这并不如在amount列上部分索引有效,因为系统必须扫描整个索引。然而,如果有相对较少的未上账订单,使用这个部分索引来查找未上账订单将会更好。

    注意这个查询将不会使用该索引:

    SELECT * FROM orders WHERE order_nr = 3501;
    

    订单3501可能在已上账订单或未上账订单中。

    假设我们有一个描述测试结果的表。我们希望保证其中对于一个给定的主题和目标组合只有一个“成功”项,但其中可能会有任意多个“不成功”项。实现它的方式是:

    CREATE TABLE tests (
        subject text,
        target text,
        success boolean,
        ...
    );
    
    CREATE UNIQUE INDEX tests_success_constraint ON tests (subject, target)
        WHERE success;
    

    当有少数成功测试和很多不成功测试时这是一种特别有效的方法。

    通过使用部分索引子句只处理空列值,该索引只允许索引列中有一个空值,并且用一个表达式索引子句来索引 true 来替代 null:

    CREATE UNIQUE INDEX tests_target_one_null ON tests ((target IS NULL)) WHERE target IS NULL;
    

    最后,一个部分索引也可以被用来重载系统的查询规划选择。同样,具有特殊分布的数据集可能导致系统在它并不需要索引的时候选择使用索引。在此种情况下可以被建立,这样它将不会被那些无关的查询所用。通常,PostgreSQL会对索引使用做出合理的选择(例如,它会在检索公值时避开索引,这样前面的例子只能节约索引尺寸,它并非是避免索引使用所必需的),非常不正确的规划选择则需要作为故障报告。

    记住建立一个部分索引意味着我们知道的至少和查询规划器所知的一样多,尤其是我们知道什么时候一个索引会是有益的。构建这些知识需要经验和对于PostgreSQL中索引工作方式的理解。在大部分情况下,一个部分索引相对于一个普通索引的优势很小。


    索引和排序规则

    一个索引在每一个索引列上只能支持一种排序规则。如果需要多种排序规则,你可能需要多个索引。

    考虑这些语句:

    CREATE TABLE test1c (
        id integer,
        content varchar COLLATE "x"
    );
    
    CREATE INDEX test1c_content_index ON test1c (content);
    

    该索引自动使用下层列的排序规则。因此一个如下形式的查询:

    SELECT * FROM test1c WHERE content > constant;
    

    可以使用该索引,因为比较会默认使用列的排序规则。但是,这个索引无法加速涉及到某些其他排序规则的查询。因此对于下面形式的查询:

    SELECT * FROM test1c WHERE content > constant COLLATE "y";
    

    可以创建一个额外的支持"y"排序规则的索引,例如:

    CREATE INDEX test1c_content_y_index ON test1c (content COLLATE "y");
    
    展开全文
  • 浅析MysQL B-Tree 索引

    2021-01-19 21:38:57
    看完上面的文章就可以理解为何B-Tree索引能够快速访问数据了。因为存储引擎不再需要进行全表扫描获取需要的数据,叶子节点包含了所有元素信息,每一个叶子节点指针都指向下一个节点,所以很适合查找范围数据。 索引...
  • PostgreSQL的B-tree索引

    千次阅读 2019-06-06 22:31:42
    B-tree索引适合用于存储排序的数据。对于这种数据类型需要定义大于、大于等于、小于、小于等于操作符。 通常情况下,B-tree的索引记录存储在数据页中。叶子页中的记录包含索引数据(keys)以及指向heap tuple记录...

    B-tree索引适合用于存储排序的数据。对于这种数据类型需要定义大于、大于等于、小于、小于等于操作符。

    通常情况下,B-tree的索引记录存储在数据页中。叶子页中的记录包含索引数据(keys)以及指向heap tuple记录(即表的行记录TIDs)的指针。内部页中的记录包含指向索引子页的指针和子页中最小值。

    B-tree有几点重要的特性:

    1、B-tree是平衡树,即每个叶子页到root页中间有相同个数的内部页。因此查询任何一个值的时间是相同的。

    2、B-tree中一个节点有多个分支,即每页(通常8KB)具有许多TIDs。因此B-tree的高度比较低,通常4到5层就可以存储大量行记录。

    3、索引中的数据以非递减的顺序存储(页之间以及页内都是这种顺序),同级的数据页由双向链表连接。因此不需要每次都返回root,通过遍历链表就可以获取一个有序的数据集。

    下面是一个索引的简单例子,该索引存储的记录为整型并只有一个字段:

    该索引最顶层的页是元数据页,该数据页存储索引root页的相关信息。内部节点位于root下面,叶子页位于最下面一层。向下的箭头表示由叶子节点指向表记录(TIDs)。

    等值查询

    例如通过"indexed-field = expression"形式的条件查询49这个值。

    root节点有三个记录:(4,32,64)。从root节点开始进行搜索,由于32≤ 49 < 64,所以选择32这个值进入其子节点。通过同样的方法继续向下进行搜索一直到叶子节点,最后查询到49这个值。

    实际上,查询算法远不止看上去的这么简单。比如,该索引是非唯一索引时,允许存在许多相同值的记录,并且这些相同的记录不止存放在一个页中。此时该如何查询?我们返回到上面的的例子,定位到第二层节点(32,43,49)。如果选择49这个值并向下进入其子节点搜索,就会跳过前一个叶子页中的49这个值。因此,在内部节点进行等值查询49时,定位到49这个值,然后选择49的前一个值43,向下进入其子节点进行搜索。最后,在底层节点中从左到右进行搜索。

    (另外一个复杂的地方是,查询的过程中树结构可能会改变,比如分裂)

    非等值查询

    通过"indexed-field ≤ expression" (or "indexed-field ≥ expression")查询时,首先通过"indexed-field = expression"形式进行等值(如果存在该值)查询,定位到叶子节点后,再向左或向右进行遍历检索。

    下图是查询 n ≤ 35的示意图:

    大于和小于可以通过同样的方法进行查询。查询时需要排除等值查询出的值。

    范围查询

     范围查询"expression1 ≤ indexed-field ≤ expression2"时,需要通过 "expression1 ≤ indexed-field =expression2"找到一匹配值,然后在叶子节点从左到右进行检索,一直到不满足"indexed-field ≤ expression2" 的条件为止;或者反过来,首先通过第二个表达式进行检索,在叶子节点定位到该值后,再从右向左进行检索,一直到不满足第一个表达式的条件为止。

    下图是23 ≤ n ≤ 64的查询示意图:

    案例

    下面是一个查询计划的实例。通过demo database中的aircraft表进行介绍。该表有9行数据,由于整个表只有一个数据页,所以执行计划不会使用索引。为了解释说明问题,我们使用整个表进行说明。

    demo=# select * from aircrafts;
     aircraft_code |        model        | range
    ---------------+---------------------+-------
     773           | Boeing 777-300      | 11100
     763           | Boeing 767-300      |  7900
     SU9           | Sukhoi SuperJet-100 |  3000
     320           | Airbus A320-200     |  5700
     321           | Airbus A321-200     |  5600
     319           | Airbus A319-100     |  6700
     733           | Boeing 737-300      |  4200
     CN1           | Cessna 208 Caravan  |  1200
     CR2           | Bombardier CRJ-200  |  2700
    (9 rows)
    demo=# create index on aircrafts(range);
    demo=# set enable_seqscan = off;
    

    (更准确的方式:create index on aircrafts using btree(range),创建索引时默认构建B-tree索引。)

    等值查询的执行计划:

    demo=# explain(costs off) select * from aircrafts where range = 3000;
                        QUERY PLAN                     
    ---------------------------------------------------
     Index Scan using aircrafts_range_idx on aircrafts
       Index Cond: (range = 3000)
    (2 rows)

    非等值查询的执行计划:

    demo=# explain(costs off) select * from aircrafts where range < 3000;
                        QUERY PLAN                    
    ---------------------------------------------------
     Index Scan using aircrafts_range_idx on aircrafts
       Index Cond: (range < 3000)
    (2 rows)

    范围查询的执行计划:

    demo=# explain(costs off) select * from aircrafts
    where range between 3000 and 5000;
                         QUERY PLAN                      
    -----------------------------------------------------
     Index Scan using aircrafts_range_idx on aircrafts
       Index Cond: ((range >= 3000) AND (range <= 5000))
    (2 rows)

    排序

    再次强调,通过index、index-only或bitmap扫描,btree访问方法可以返回有序的数据。因此如果表的排序条件上有索引,优化器会考虑以下方式:表的索引扫描;表的顺序扫描然后对结果集进行排序。

    排序顺序

    当创建索引时可以明确指定排序顺序。如下所示,在range列上建立一个索引,并且排序顺序为降序:

    demo=# create index on aircrafts(range desc);

    本案例中,大值会出现在树的左边,小值出现在右边。为什么有这样的需求?这样做是为了多列索引。创建aircraft的一个视图,通过range分成3部分:

    demo=# create view aircrafts_v as
    select model,
           case
               when range < 4000 then 1
               when range < 10000 then 2
               else 3
           end as class
    from aircrafts;
    
    
    demo=# select * from aircrafts_v;
            model        | class
    ---------------------+-------
     Boeing 777-300      |     3
     Boeing 767-300      |     2
     Sukhoi SuperJet-100 |     1
     Airbus A320-200     |     2
     Airbus A321-200     |     2
     Airbus A319-100     |     2
     Boeing 737-300      |     2
     Cessna 208 Caravan  |     1
     Bombardier CRJ-200  |     1
    (9 rows)

    然后创建一个索引(使用下面表达式):

    demo=# create index on aircrafts(
      (case when range < 4000 then 1 when range < 10000 then 2 else 3 end),
      model);

    现在,可以通过索引以升序的方式获取排序的数据:

    demo=# select class, model from aircrafts_v order by class, model;
     class |        model        
    -------+---------------------
         1 | Bombardier CRJ-200
         1 | Cessna 208 Caravan
         1 | Sukhoi SuperJet-100
         2 | Airbus A319-100
         2 | Airbus A320-200
         2 | Airbus A321-200
         2 | Boeing 737-300
         2 | Boeing 767-300
         3 | Boeing 777-300
    (9 rows)
    
    
    demo=# explain(costs off)
    select class, model from aircrafts_v order by class, model;
                           QUERY PLAN                       
    --------------------------------------------------------
     Index Scan using aircrafts_case_model_idx on aircrafts
    (1 row)

    同样,可以以降序的方式获取排序的数据:

    demo=# select class, model from aircrafts_v order by class desc, model desc;
     class |        model        
    -------+---------------------
         3 | Boeing 777-300
         2 | Boeing 767-300
         2 | Boeing 737-300
         2 | Airbus A321-200
         2 | Airbus A320-200
         2 | Airbus A319-100
         1 | Sukhoi SuperJet-100
         1 | Cessna 208 Caravan
         1 | Bombardier CRJ-200
    (9 rows)
    demo=# explain(costs off)
    select class, model from aircrafts_v order by class desc, model desc;
                               QUERY PLAN                            
    -----------------------------------------------------------------
     Index Scan BACKWARD using aircrafts_case_model_idx on aircrafts
    (1 row)

    然而,如果一列以升序一列以降序的方式获取排序的数据的话,就不能使用索引,只能单独排序:

    demo=# explain(costs off)
    select class, model from aircrafts_v order by class ASC, model DESC;
                       QUERY PLAN                    
    -------------------------------------------------
     Sort
       Sort Key: (CASE ... END), aircrafts.model DESC
       ->  Seq Scan on aircrafts
    (3 rows)

    (注意,最终执行计划会选择顺序扫描,忽略之前设置的enable_seqscan = off。因为这个设置并不会放弃表扫描,只是设置他的成本----查看costs on的执行计划)

    若有使用索引,创建索引时指定排序的方向:

    demo=# create index aircrafts_case_asc_model_desc_idx on aircrafts(
     (case
        when range < 4000 then 1
        when range < 10000 then 2
        else 3
      end) ASC,
      model DESC);
    
    
    demo=# explain(costs off)
    select class, model from aircrafts_v order by class ASC, model DESC;
                               QUERY PLAN                            
    -----------------------------------------------------------------
     Index Scan using aircrafts_case_asc_model_desc_idx on aircrafts
    (1 row)

    列的顺序

    当使用多列索引时与列的顺序有关的问题会显示出来。对于B-tree,这个顺序非常重要:页中的数据先以第一个字段进行排序,然后再第二个字段,以此类推。

    下图是在range和model列上构建的索引:

     

    当然,上图这么小的索引在一个root页足以存放。但是为了清晰起见,特意将其分成几页。

    从图中可见,通过类似的谓词class = 3(仅按第一个字段进行搜索)或者class = 3 and model = 'Boeing 777-300'(按两个字段进行搜索)将非常高效。

    然而,通过谓词model = 'Boeing 777-300'进行搜索的效率将大大降低:从root开始,判断不出选择哪个子节点进行向下搜索,因此会遍历所有子节点向下进行搜索。这并不意味着永远无法使用这样的索引----它的效率有问题。例如,如果aircraft有3个classes值,每个class类中有许多model值,此时不得不扫描索引1/3的数据,这可能比全表扫描更有效。

    但是,当创建如下索引时:

    demo=# create index on aircrafts(
      model,
      (case when range < 4000 then 1 when range < 10000 then 2 else 3 end));

    索引字段的顺序会改变:

     

    通过这个索引,model = 'Boeing 777-300'将会很有效,但class = 3则没这么高效。

    NULLs

    PostgreSQL的B-tree支持在NULLs上创建索引,可以通过IS NULL或者IS NOT NULL的条件进行查询。

    考虑flights表,允许NULLs:

    demo=# create index on flights(actual_arrival);
    demo=# explain(costs off) select * from flights where actual_arrival is null;
                          QUERY PLAN                       
    -------------------------------------------------------
     Bitmap Heap Scan on flights
       Recheck Cond: (actual_arrival IS NULL)
       ->  Bitmap Index Scan on flights_actual_arrival_idx
             Index Cond: (actual_arrival IS NULL)
    (4 rows)

    NULLs位于叶子节点的一端或另一端,这依赖于索引的创建方式(NULLS FIRST或NULLS LAST)。如果查询中包含排序,这就显得很重要了:如果SELECT语句在ORDER BY子句中指定NULLs的顺序索引构建的顺序一样(NULLS FIRST或NULLS LAST),就可以使用整个索引。

    下面的例子中,他们的顺序相同,因此可以使用索引:

    demo=# explain(costs off)
    select * from flights order by actual_arrival NULLS LAST;
                           QUERY PLAN                      
    --------------------------------------------------------
     Index Scan using flights_actual_arrival_idx on flights
    (1 row)

    下面的例子,顺序不同,优化器选择顺序扫描然后进行排序:

    demo=# explain(costs off)
    select * from flights order by actual_arrival NULLS FIRST;
                   QUERY PLAN              
    ----------------------------------------
     Sort
       Sort Key: actual_arrival NULLS FIRST
       ->  Seq Scan on flights
    (3 rows)

    NULLs必须位于开头才能使用索引:

    demo=# create index flights_nulls_first_idx on flights(actual_arrival NULLS FIRST);
    demo=# explain(costs off)
    select * from flights order by actual_arrival NULLS FIRST;
                         QUERY PLAN                      
    -----------------------------------------------------
     Index Scan using flights_nulls_first_idx on flights
    (1 row)

    像这样的问题是由NULLs引起的而不是无法排序,也就是说NULL和其他这比较的结果无法预知:

    demo=# \pset null NULL
    demo=# select null < 42;
     ?column?
    ----------
     NULL
    (1 row)

    这和B-tree的概念背道而驰并且不符合一般的模式。然而NULLs在数据库中扮演者很重要的角色,因此不得不为NULL做特殊设置。

    由于NULLs可以被索引,因此即使表上没有任何标记也可以使用索引。(因为这个索引包含表航记录的所有信息)。如果查询需要排序的数据,而且索引确保了所需的顺序,那么这可能是由意义的。这种情况下,查询计划更倾向于通过索引获取数据。

    属性

    下面介绍btree访问方法的特性。

     amname |     name      | pg_indexam_has_property
    --------+---------------+-------------------------
     btree  | can_order     | t
     btree  | can_unique    | t
     btree  | can_multi_col | t
     btree  | can_exclude   | t

    可以看到,B-tree能够排序数据并且支持唯一性。同时还支持多列索引,但是其他访问方法也支持这种索引。我们将在下次讨论EXCLUDE条件。

         name      | pg_index_has_property
    ---------------+-----------------------
     clusterable   | t
     index_scan    | t
     bitmap_scan   | t
     backward_scan | t

    Btree访问方法可以通过以下两种方式获取数据:index scan以及bitmap scan。可以看到,通过tree可以向前和向后进行遍历。

          name          | pg_index_column_has_property
    --------------------+------------------------------
     asc                | t
     desc               | f
     nulls_first        | f
     nulls_last         | t
     orderable          | t
     distance_orderable | f
     returnable         | t
     search_array       | t
     search_nulls       | t
    

    前四种特性指定了特定列如何精确的排序。本案例中,值以升序(asc)进行排序并且NULLs在后面(nulls_last)。也可以有其他组合。

    search_array的特性支持向这样的表达式:

    demo=# explain(costs off)
    select * from aircrafts where aircraft_code in ('733','763','773');
                               QUERY PLAN                            
    -----------------------------------------------------------------
     Index Scan using aircrafts_pkey on aircrafts
       Index Cond: (aircraft_code = ANY ('{733,763,773}'::bpchar[]))
    (2 rows)

    returnable属性支持index-only scan,由于索引本身也存储索引值所以这是合理的。下面简单介绍基于B-tree的覆盖索引。

    具有额外列的唯一索引

    前面讨论了:覆盖索引包含查询所需的所有值,需不要再回表。唯一索引可以成为覆盖索引。

    假设我们查询所需要的列添加到唯一索引,新的组合唯一键可能不再唯一,同一列上将需要2个索引:一个唯一,支持完整性约束;另一个是非唯一,为了覆盖索引。这当然是低效的。

    在我们公司 Anastasiya Lubennikova @ lubennikovaav 改进了btree,额外的非唯一列可以包含在唯一索引中。我们希望这个补丁可以被社区采纳。实际上PostgreSQL11已经合了该补丁。

    考虑表bookings:d

    demo=# \d bookings
                  Table "bookings.bookings"
        Column    |           Type           | Modifiers
    --------------+--------------------------+-----------
     book_ref     | character(6)             | not null
     book_date    | timestamp with time zone | not null
     total_amount | numeric(10,2)            | not null
    Indexes:
        "bookings_pkey" PRIMARY KEY, btree (book_ref)
    Referenced by:
    TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)

    这个表中,主键(book_ref,booking code)通过常规的btree索引提供,下面创建一个由额外列的唯一索引:

    demo=# create unique index bookings_pkey2 on bookings(book_ref) INCLUDE (book_date);

    然后使用新索引替代现有索引:

    demo=# begin;
    demo=# alter table bookings drop constraint bookings_pkey cascade;
    demo=# alter table bookings add primary key using index bookings_pkey2;
    demo=# alter table tickets add foreign key (book_ref) references bookings (book_ref);
    demo=# commit;

    然后表结构:

    demo=# \d bookings
                  Table "bookings.bookings"
        Column    |           Type           | Modifiers
    --------------+--------------------------+-----------
     book_ref     | character(6)             | not null
     book_date    | timestamp with time zone | not null
     total_amount | numeric(10,2)            | not null
    Indexes:
        "bookings_pkey2" PRIMARY KEY, btree (book_ref) INCLUDE (book_date)
    Referenced by:
    TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)

    此时,这个索引可以作为唯一索引工作也可以作为覆盖索引:

    demo=# explain(costs off)
    select book_ref, book_date from bookings where book_ref = '059FC4';
                        QUERY PLAN                    
    --------------------------------------------------
     Index Only Scan using bookings_pkey2 on bookings
       Index Cond: (book_ref = '059FC4'::bpchar)
    (2 rows)

    创建索引

    众所周知,对于大表,加载数据时最好不要带索引;加载完成后再创建索引。这样做不仅提升效率还能节省空间。

    创建B-tree索引比向索引中插入数据更高效。所有的数据大致上都已排序,并且数据的叶子页已创建好,然后只需构建内部页直到root页构建成一个完整的B-tree。

    这种方法的速度依赖于RAM的大小,受限于参数maintenance_work_mem。因此增大该参数值可以提升速度。对于唯一索引,除了分配maintenance_work_mem的内存外,还分配了work_mem的大小的内存。

    比较

    前面,提到PG需要知道对于不同类型的值调用哪个函数,并且这个关联方法存储在哈希访问方法中。同样,系统必须找出如何排序。这在排序、分组(有时)、merge join中会涉及。PG不会将自身绑定到操作符名称,因为用户可以自定义他们的数据类型并给出对应不同的操作符名称。

    例如bool_ops操作符集中的比较操作符:

    postgres=# select   amop.amopopr::regoperator as opfamily_operator,
             amop.amopstrategy
    from     pg_am am,
             pg_opfamily opf,
             pg_amop amop
    where    opf.opfmethod = am.oid
    and      amop.amopfamily = opf.oid
    and      am.amname = 'btree'
    and      opf.opfname = 'bool_ops'
    order by amopstrategy;
      opfamily_operator  | amopstrategy
    ---------------------+--------------
     <(boolean,boolean)  |            1
     <=(boolean,boolean) |            2
     =(boolean,boolean)  |            3
     >=(boolean,boolean) |            4
     >(boolean,boolean)  |            5
    (5 rows)

    这里可以看到有5种操作符,但是不应该依赖于他们的名字。为了指定哪种操作符做什么操作,引入策略的概念。为了描述操作符语义,定义了5种策略:

            1 — less

            2 — less or equal

            3 — equal

            4 — greater or equal

            5 — greater

    postgres=# select   amop.amopopr::regoperator as opfamily_operator
    from     pg_am am,
             pg_opfamily opf,
             pg_amop amop
    where    opf.opfmethod = am.oid
    and      amop.amopfamily = opf.oid
    and      am.amname = 'btree'
    and      opf.opfname = 'integer_ops'
    and      amop.amopstrategy = 1
    order by opfamily_operator;
      pfamily_operator  
    ----------------------
     <(integer,bigint)
     <(smallint,smallint)
     <(integer,integer)
     <(bigint,bigint)
     <(bigint,integer)
     <(smallint,integer)
     <(integer,smallint)
     <(smallint,bigint)
     <(bigint,smallint)
    (9 rows)
    
    

    一些操作符族可以包含几种操作符,例如integer_ops包含策略1的几种操作符:

    正因如此,当比较类型在一个操作符族中时,不同类型值的比较,优化器可以避免类型转换。

    索引支持的新数据类型

    文档中提供了一个创建符合数值的新数据类型,以及对这种类型数据进行排序的操作符类。该案例使用C语言完成。但不妨碍我们使用纯SQL进行对比试验。

    创建一个新的组合类型:包含real和imaginary两个字段

    postgres=# create type complex as (re float, im float);

    创建一个包含该新组合类型字段的表:

    postgres=# create table numbers(x complex);
    postgres=# insert into numbers values ((0.0, 10.0)), ((1.0, 3.0)), ((1.0, 1.0));

    现在有个疑问,如果在数学上没有为他们定义顺序关系,如何进行排序?

    已经定义好了比较运算符:

    postgres=# select * from numbers order by x;
       x    
    --------
     (0,10)
     (1,1)
     (1,3)
    (3 rows)

    默认情况下,对于组合类型排序是分开的:首先比较第一个字段然后第二个字段,与文本字符串比较方法大致相同。但是我们也可以定义其他的排序方式,例如组合数字可以当做一个向量,通过模值进行排序。为了定义这样的顺序,我们需要创建一个函数:

    postgres=# create function modulus(a complex) returns float as $$
        select sqrt(a.re*a.re + a.im*a.im);
    $$ immutable language sql;
    
    
    //此时,使用整个函数系统的定义5种操作符:
    postgres=# create function complex_lt(a complex, b complex) returns boolean as $$
        select modulus(a) < modulus(b);
    $$ immutable language sql;
    
    postgres=# create function complex_le(a complex, b complex) returns boolean as $$
        select modulus(a) <= modulus(b);
    $$ immutable language sql;
    
    postgres=# create function complex_eq(a complex, b complex) returns boolean as $$
        select modulus(a) = modulus(b);
    $$ immutable language sql;
    
    postgres=# create function complex_ge(a complex, b complex) returns boolean as $$
        select modulus(a) >= modulus(b);
    $$ immutable language sql;
    
    postgres=# create function complex_gt(a complex, b complex) returns boolean as $$
        select modulus(a) > modulus(b);
    $$ immutable language sql;

    然后创建对应的操作符:

    postgres=# create operator #<#(leftarg=complex, rightarg=complex, procedure=complex_lt);
    postgres=# create operator #<=#(leftarg=complex, rightarg=complex, procedure=complex_le);
    postgres=# create operator #=#(leftarg=complex, rightarg=complex, procedure=complex_eq);
    postgres=# create operator #>=#(leftarg=complex, rightarg=complex, procedure=complex_ge);
    postgres=# create operator #>#(leftarg=complex, rightarg=complex, procedure=complex_gt);

    此时,可以比较数字:

    postgres=# select (1.0,1.0)::complex #<# (1.0,3.0)::complex;
     ?column?
    ----------
     t
    (1 row)

    除了整个5个操作符,还需要定义函数:小于返回-1;等于返回0;大于返回1。其他访问方法可能需要定义其他函数:

    postgres=# create function complex_cmp(a complex, b complex) returns integer as $$
        select case when modulus(a) < modulus(b) then -1
                    when modulus(a) > modulus(b) then 1
                    else 0
               end;
    $$ language sql;

    创建一个操作符类:

    postgres=# create operator class complex_ops
    default for type complex
    using btree as
        operator 1 #<#,
        operator 2 #<=#,
        operator 3 #=#,
        operator 4 #>=#,
        operator 5 #>#,
    function 1 complex_cmp(complex,complex);
    
    //排序结果:
    postgres=# select * from numbers order by x;
       x    
    --------
     (1,1)
     (1,3)
     (0,10)
    (3 rows)
    
    //可以使用此查询获取支持的函数:
    
    postgres=# select amp.amprocnum,
           amp.amproc,
           amp.amproclefttype::regtype,
           amp.amprocrighttype::regtype
    from   pg_opfamily opf,
           pg_am am,
           pg_amproc amp
    where  opf.opfname = 'complex_ops'
    and    opf.opfmethod = am.oid
    and    am.amname = 'btree'
    and    amp.amprocfamily = opf.oid;
     amprocnum |   amproc    | amproclefttype | amprocrighttype
    -----------+-------------+----------------+-----------------
             1 | complex_cmp | complex        | complex
    (1 row)

    内部结构

    使用pageinspect插件观察B-tree结构:

    demo=# create extension pageinspect;

    索引的元数据页:

    demo=# select * from bt_metap('ticket_flights_pkey');
     magic  | version | root | level | fastroot | fastlevel
    --------+---------+------+-------+----------+-----------
     340322 |       2 |  164 |     2 |      164 |         2
    (1 row)

    值得关注的是索引level:不包括root,有一百万行记录的表其索引只需要2层就可以了。

    Root页,即164号页面的统计信息:

    demo=# select type, live_items, dead_items, avg_item_size, page_size, free_size
    from bt_page_stats('ticket_flights_pkey',164);
     type | live_items | dead_items | avg_item_size | page_size | free_size
    ------+------------+------------+---------------+-----------+-----------
     r    |         33 |          0 |            31 |      8192 |      6984
    (1 row)

    该页中数据:

    demo=# select itemoffset, ctid, itemlen, left(data,56) as data
    from bt_page_items('ticket_flights_pkey',164) limit 5;
     itemoffset |  ctid   | itemlen |                           data                           
    ------------+---------+---------+----------------------------------------------------------
              1 | (3,1)   |       8 |
              2 | (163,1) |      32 | 1d 30 30 30 35 34 33 32 33 30 35 37 37 31 00 00 ff 5f 00
              3 | (323,1) |      32 | 1d 30 30 30 35 34 33 32 34 32 33 36 36 32 00 00 4f 78 00
              4 | (482,1) |      32 | 1d 30 30 30 35 34 33 32 35 33 30 38 39 33 00 00 4d 1e 00
              5 | (641,1) |      32 | 1d 30 30 30 35 34 33 32 36 35 35 37 38 35 00 00 2b 09 00
    (5 rows)

    第一个tuple指定该页的最大值,真正的数据从第二个tuple开始。很明显最左边子节点的页号是163,然后是323。反过来,可以使用相同的函数搜索。

    PG10版本提供了"amcheck"插件,该插件可以检测B-tree数据的逻辑一致性,使我们提前探知故障。

    原文

    https://habr.com/en/company/postgrespro/blog/443284/

    展开全文
  • PostgreSQL中的B-tree索引

    千次阅读 2018-10-09 10:56:06
    索引是提高数据库性能的常用途径。比起没有索引,使用索引可以让数据库服务器更快找到并获取特定行。但是索引同时也会增加数据库系统的日常管理负担,因此我们应该聪明地使用索引索引简介 在数据库中,一旦一个...

    索引是提高数据库性能的常用途径。比起没有索引,使用索引可以让数据库服务器更快找到并获取特定行。但是索引同时也会增加数据库系统的日常管理负担,因此我们应该聪明地使用索引。

    索引简介

    在数据库中,一旦一个索引被创建,就不再需要进一步的干预:系统会在表更新时更新索引,而且会在它觉得使用索引比顺序扫描表效率更高时使用索引。但我们可能需要定期地运行ANALYZE命令来更新统计信息以便查询规划器能做出正确的决定。

    索引也会使带有搜索条件的UPDATE和DELETE命令受益。此外索引还可以在连接搜索中使用。因此,一个定义在连接条件列上的索引可以显著地提高连接查询的速度。

    在一个大表上创建一个索引会耗费很长的时间。默认情况下,PostgreSQL允许在索引创建时并行地进行读(SELECT命令),但写(INSERT、UPDATE和DELETE)则会被阻塞直到索引创建完成。在生产环境中这通常是不可接受的。在创建索引时允许并行的写是可能的,但是有些警告需要注意,更多信息可以参考下文中的并发构建索引。

    一个索引被创建后,系统必须保持它与表同步。这增加了数据操作的负担。因此哪些很少或从不在查询中使用的索引应该被移除。

    B-tree索引

    postgresql支持多种索引类型,每一种索引类型使用了 一种不同的算法来适应不同类型的查询。默认情况下, CREATE INDEX命令创建适合于大部分情况的B-tree 索引。
    B-tree用于在可排序数据上等值及范围查询。特别地,PostgreSQL的查询规划器会在任何一种涉及到以下操作符的已索引列上考虑使用B-tree索引:

    <	<=	=	>=	>
    

    将这些操作符组合起来,例如BETWEEN和IN,也可以用B-tree索引搜索实现。同样,在索引列上的IS NULLIS NOT NULL条件也可以在B-tree索引中使用。B-tree索引也可以用于涉及到模式匹配操作符LIKE和~ 的查询,前提是如果模式是一个常量且被固定在字符串的开头。
    补充:主键和唯一键会自动创建B-tree索引,无需另外单独再为主键和唯一键创建索引。
    关于B-tree索引的理论,可参考文章:https://www.cnblogs.com/bypp/p/7755307.html中的介绍。

    多列索引

    一个索引可以定义在表的多个列上。例如,我们有这样一个表:

    CREATE TABLE test2 (
      major int,
      minor int,
      name varchar
    );
    

    而我们经常会做如下形式的查询:

    SELECT name FROM test2 WHERE major = constant AND minor = constant;
    

    那么我们可以在major和minor上定义一个索引:

    CREATE INDEX test2_mm_idx ON test2 (major, minor);
    

    当使用多列索引时,有以下规则(也被称为最左匹配特性):在先导列(即最左边的那些列)上的等值约束,加上第一个无等值约束的列上的不等值约束,将被用于限制索引被扫描的部分。在这些列右边的列上的约束将在索引中被检查,这样它们适当节约了对表的访问,但它们并未减小索引被扫描的部分。
    用自己的话说,就是尽量将具有等值约束的索引放在最左边,以减少索引被扫描的范围,从而节约时间。
    例如,在(a, b, c)上有一个索引并且给定一个查询条件WHERE a = 5 AND b >= 42 AND c < 77,对索引的扫描将从第一个具有a = 5和b = 42的项开始向上进行,直到最后一个具有a = 5的项。在扫描过程中,具有c >= 77的索引项将被跳过,但是它们还是会被扫描到。这个索引在原则上可以被用于在b和、或c上有约束而在a上没有约束的查询,但是整个索引都不得不被扫描,因此在大部分情况下规划器宁可使用一个顺序的表扫描来替代索引。

    多列索引应该较少地使用。在绝大多数情况下,单列索引就足够了且能解决时间和空间。具有超过三个列的索引不太有用,除非该表的使用是极端程式化的。

    表达式索引

    一个索引列并不一定是底层表的一个列,也可以是从表的一列或多列计算而来的一个函数或者标量表达式。这种特性对于根据计算结果快速获取表中内容是有用的。

    例如,一种进行大小写不敏感比较的常用方法是使用lower函数:

    SELECT * FROM test1 WHERE lower(col1) = 'value';
    

    这种查询可以利用一个建立在lower(col1)函数结果之上的索引:

    CREATE INDEX test1_lower_col1_idx ON test1 (lower(col1));
    

    如果我们将该索引声明为UNIQUE,它将阻止创建在col1值上只有大小写不同的行。

    索引表达式的维护代价较为昂贵,因为在每一个行被插入或更新时都得为它重新计算相应的表达式。然而,索引表达式在进行索引搜索时却不需要重新计算,因为它们的结果已经被存储在索引中了。在上面两个例子中,系统将会发现查询的条件是WHERE indexedcolumn = ‘constant’,因此查询的速度将等同于其他简单索引查询。因此,表达式索引对于检索速度远比插入和更新速度重要的情况非常有用。

    检查使用索引

    尽管PostgreSQL中的索引并不需要维护或调优,但是检查真实的查询负载实际使用了哪些索引仍然非常重要。检查一个独立查询的索引使用情况可以使用EXPLAIN命令,也可以在一个运行中的服务器上收集有关索引使用的总体统计情况。
    很难明确地表达决定创建哪些索引的通用过程。通常需要大量的实验才能决定应该创建哪些索引。对于创建和使用索引有以下提示:
    1.总是先运行ANALYZE。这个命令会收集有关表中值分布情况的统计信息。估计一个查询将要返回的行数需要这些信息,而结果行数则被规划器用来为每一个可能的查询计划分配实际的代价。如果没有任何真实的统计信息,将会假定一些默认值,这几乎肯定是不准确的。在没有运行的情况下检查一个应用的索引使用情况是注定要失败的。
    2.使用真实数据进行实验。避免使用很小的数据量来测试索引。
    3.如果索引没有被用到,强制使用它们将会对测试非常有用。
    4.如果强制索引使用确实使用了索引,则有两种可能性:系统是正确的并且索引确实不合适,或者查询计划的代价估计并没有反映真实情况。因此你应该对用索引的查询和不用索引的查询计时。此时EXPLAIN ANALYZE命令就能发挥作用了。
    5.如果发现代价估计是错误的,也分为两种可能性。总代价是用每个计划节点的每行代价乘以计划节点的选择度估计来计算的。计划节点的代价估计可以通过运行时参数调整。不准确的选择度估计可能是由于缺乏统计信息,可以通过调节统计信息收集参数来改进。

    并发构建索引

    创建索引可能会干扰数据库的常规操作。通常 PostgreSQL会锁住要被索引的表,让它不能被写入, 并且用该表上的一次扫描来执行整个索引的构建。其他事务仍然可以读取表 , 但是如果它们尝试在该表上进行插入、更新或者删除,它们会被阻塞直到索引 构建完成。如果系统是一个生产数据库,这可能会导致严重的后果。索引非常 大的表可能会需要很多个小时,而且即使是较小的表,在构建索引过程中阻塞 写入者一段时间在生产系统中也是不能接受的。

    PostgreSQL支持构建索引时不阻塞写入。这种方法通过指定CREATE INDEX的CONCURRENTLY选项实现。当使用这个选项时,PostgreSQL必须执行该表的两次扫描,此外它必须等待所有现有可能会修改或者使用该索引的事务终止。因此这种方法比起标准索引构建过程来说要做更多工作并且需要更多时间。不过,由于它 允许在构建索引时继续普通操作,这种方式对于在生产环境中增加新索引很有用。 当然,由索引创建带来的额外 CPU 和 I/O 开销可能会拖慢其他操作。

    在并发索引构建中,索引实际上在一个事务中被录入到系统目录,然后在两个事务中发生两次表扫描。在每一次表扫描之前,索引构建必须等待已经修改了 表的现有事务终止。在第二次扫描之后,索引构建必须等待任何持有早于第二次扫描的快照的事务终止。然后该索引最终 能被标记为准备好使用,并且CREATE INDEX命令终止。 不过即便那样,该索引也不是立刻可以用于查询:在最坏的情况下,只要早于索引构建开始时存在的事务存在,该索引就无法使用。

    如果在扫描表示出现问题,例如死锁或者唯一索引中的唯一性被违背, CREATE INDEX将会失败,但留下一个"不可用" 的索引。这个索引会被查询所忽略,因为它可能不完整。不过它仍将消耗更新开销。psql的\d命令将把这类索引报告为 INVALID:

    postgres=# \d tab
           Table "public.tab"
     Column |  Type   | Modifiers 
    --------+---------+-----------
     col    | integer | 
    Indexes:
        "idx" btree (col) INVALID
    

    这种情况下推荐的恢复方法是删除该索引并且尝试再次执行 CREATE INDEX CONCURRENTLY(另一种可能性是用 REINDEX重建该索引。不过,由于 REINDEX不支持并发构建,这种选择不那么有吸引力)。

    并发构建一个唯一索引时需要注意的另一点是,当第二次表扫描开始时,唯一约束已经被强制在其他事务上。这意味着在该索引变得可用之前,其他查询中可能就会报告该约束被违背,或者甚至在索引构建最终失败的情况中也是这样。还有,如果在 第二次扫描时发生失败,"无效的"索引也会继续强制它的唯一性约束。

    表达式索引和部分索引的并发构建也被支持。在这些表达式计算过程中发生的错误可能导致和上述唯一约束违背类似的行为。

    常规索引构建允许在同一个表上并行构建其他常规索引,但是在一个表上同时只能有一个并发索引构建发生。在两种情况下,同时都不允许在表上有其他类 型的模式修改。另一个不同是,一个常规CREATE INDEX 命令可以在一个事务块中执行,但是 CREATE INDEX CONCURRENTLY不行。

    参考:
    http://www.postgres.cn/docs/9.6/indexes.html

    展开全文
  • 现在,我们知道优化器如何对这些技术做出反应,清楚地说明 bitmap 索引B-tree 索引各自的最好应用。 在 GENDER 列适当地带一个 bitmap 索引,在 SAL 列上创建另外一个位图索引,然后执行一些查询。在这些列上,用...
  • B-Tree索引详解及联合索引使用

    千次阅读 2018-04-04 15:04:16
    B-Tree索引原理详解部分转载自:http://zsuil.com/?p=1184一.B-tree索引详解B-tree索引(或Balanced Tree),是一种很普遍的数据库索引结构,oracle默认的索引类型(本文也主要依据oracle来讲)。其特点是定位高效、...
  • Oracle学习 --B-tree索引

    2019-03-03 13:43:06
    根据实际情况合理使用索引能优化查询速度 查询数据大于等于数据量的百分之10 就用全表扫描 1、索引与表一样,也属于段(segment)的一种。里面存放了用户的数据,跟表一样需要占用磁盘空间。 2、索引里的数据存放...
  • 数据库索引-B-Tree索引

    千次阅读 2017-02-10 10:34:13
    1.索引简介 索引(键(key))是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键。索引优化应该是对查询性能优化最有效的手段了,索引能够轻易将查询性能提高几个数量级,“最优”的索引有时...
  • 最常见的B-Tree索引,按照顺序存储数据,所以MySQL可以用来做ORDER BY和GROUP BY操作。因为数据是有序的,所以B-Tree也就会将相关的列值都存储在一起。最后,因为索引中存储了实际的列值,所以某些查询只使用索引就...
  • B-Tree 索引

    2016-01-20 13:37:51
    1. 合理设计并利用索引 索引优化,可以说是数据库相关优化,尤其是Query 优化中最常用的优化手段之一。很多人大部分时候都只是大概了解索引的用途,知道索引能够让 Query 执行得更快,但并不知道为什么会更快。尤其...
  • Oracle学习笔记(一)——B-Tree索引

    千次阅读 2017-06-10 19:31:03
    目录是索引的一个最好的例子,每条目录包含对应章节的标题和页码,... 常常被提及的索引可能有单键索引、组合索引、唯一索引、B-Tree索引、位图索引、函数索引、全局索引、局部索引等等。这里只是列举出镜率较高的索引
  • 索引key{last_name, first_name, dob)为例 索引有效的情况: 1.全位匹配: 全值匹配指的是和索引中的所有列进行匹配, 例如前面提到的索引可用于查找姓名为CubaAllen、出生于1960-01-01 的人。 2.匹配最左前级...
  • Bitmap位图索引与普通的B-Tree索引锁的比较 通过以下实验,来验证Bitmap位图索引较之普通的B-Tree索引锁的“高昂代价”。位图索引会带来“位图段级锁”,实际使用过程一定要充分了解不同索引带来的锁代价情况。 ...
  • 在Oracle中,SYSTEM表是安装数据库时自动建立的,它包含数据库的全部数据字典,存储过程、包、函数和触发器的定义以及系统回滚段。本文只讨论Oracle中最常见的索引,即是B-tree索引
  • B-Tree 索引和 Hash 索引的对比

    万次阅读 2015-07-06 21:14:49
    对于 B-tree 和 hash 数据结构的理解能够有助于预测不同存储引擎下使用不同索引的查询性能的差异,尤其是那些允许你选择 B-tree 或者 hash 索引的内存存储引擎。B-Tree 索引的特点B-tree 索引可以用于使用 =, >, >=,...
  • NULL 博文链接:https://zzc1684.iteye.com/blog/2226223
  • NULL 博文链接:https://wlh269.iteye.com/blog/747555
  • B-tree索引:使用B-tree数据结构来存储数据(实际上一般使用的是B+tree,即每一个叶子节点都包含指向下一个叶子节点的指针,为了方便叶子节点的范围遍历)B-tree意味着所有的值都是按顺序存储的,且每一个叶子页到根...
  • mysql --- b-tree索引介绍

    2018-05-02 23:44:07
    类型:3.1 B-Tree索引3.1.1为什么使用的是b-tree而不是二叉树? 查找树有完全二叉树、二叉查找树、平衡二叉树、红黑树,B-Tree,B+-Tree,B*-Tree等。对于二叉树其目的是要将查询复杂度控制在O(lgN)以内。(注:...
  • 索引是存储引擎用来快速查找记录的一种数据结构,按照实现的方式有不同的种类,想B-Tree索引,hash索引,空间数据索引和全文索引等。下面主要说一下B-Tree索引和Hash索引。人们在谈论索引的时候如果没有特别说明,...
  • MySQL Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。...
  • 引言:大家都知道“效率”是数据库中非常重要的一个指标,如何提高效率大家可能都会想起索引,但索引又这么多种,什么场合应该使用什么索引呢?哪种索引可以提高我们的效率,哪种索引可以让我们的效率大大降低...B-...
  • Hash索引B-Tree索引 【内容】 1. Hash索引  Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash...
  • ... 这是从《MySQL性能调优与架构设计》第六章摘录的一些知识点。...Hash索引B-Tree索引 【内容】 1. Hash索引  Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定
  • MySQL索引原理及B-Tree / B+Tree结构详解

    万次阅读 2019-08-09 12:30:22
    MySQL索引原理及B-Tree / B+Tree结构详解 目录 摘要 数据结构及算法基础 索引的本质 B-Tree和B+Tree ...B-Tree ...B+Tree ...带有顺序访问指针的B+Tree ...B-/+Tree索引的性能分析 MySQL索引实现 MyISAM索引实现 Inno...
  • Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。 可能很多人又...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 92,848
精华内容 37,139
关键字:

b-tree索引