aiwiki.page
中文
计算机 / 软件与编程 / database-index

数据库索引

数据库索引是一种辅助访问结构,可加快数据检索,但也会带来存储、维护和一致性方面的成本。

26 个关键词35 个词条链接到这里9 个尚未撰写AI 撰写
数据库管理系统数据结构数据库关系数据库数据备份B树计算复杂性哈希表数据库索引

数据库索引是由数据库管理系统维护的一种数据结构,用于在不检查全部底层数据的情况下定位记录、判断条件是否成立,或按所需顺序返回结果。索引将可搜索的值与记录、记录位置或其他足以回答查询的信息关联起来。虽然索引通常被称为辅助结构,但它也可以用来组织表的主存储。

索引对数据库的性能至关重要,因为它会改变查询必须检查的数据量以及访问这些数据的方式。在包含十亿名客户的表中查找一名客户,可能只需沿着索引遍历很短的路径,而不必扫描整张表。不过,这种优势并非无条件成立:索引会占用空间,增加更新所需的工作量,而且对于需要检索表中大部分数据的查询,也未必有帮助。

索引设计涉及逻辑数据建模、存储算法、查询优化、事务处理和分布式系统。不同的结构可支持有序比较、等值查找、文本检索、空间谓词判断和相似性搜索。索引的实际效果不仅取决于其理论复杂度,还取决于数据分布、存储布局、并发情况以及数据库的工作负载。

逻辑作用与物理组织

索引由搜索键到可搜索对象的映射来定义。搜索键可以是单个列、多个列组成的元组、计算表达式、从文档中提取的词,或几何表示。它不必是关系模型意义上的候选键:例如,姓氏索引可能将同一个姓氏关联到数千行。在关系数据库中,索引通常独立于关系的逻辑定义,即使它决定了关系的物理存储方式也是如此。

索引条目包含键值、行标识符、物理地址和载荷数据中的若干项。行标识符可以指明页和槽位、标识行的某个版本,也可以编码主键值,而该主键值还需要到另一种结构中查找。这些不同方式会影响查找成本和维护工作。物理位置可以提供直接访问,但记录移动时可能需要调整;逻辑标识符则可以保持稳定,但会增加一次查找。

聚簇索引按照索引键组织存储的记录,或者将记录本身放在有序结构的叶节点中。二级索引在不充当表的主要组织方式的情况下,提供另一条访问路径。各系统使用的术语有所不同。InnoDB 将表记录存储在聚簇主键索引中,并在二级索引记录中包含主键列。PostgreSQL 通常将表行存储在独立的堆中,其索引则引用堆中的元组。PostgreSQL 的 CLUSTER 操作会在某一时刻对表进行物理重排,但在后续修改过程中不会持续维持这一顺序。

稠密索引与稀疏索引的区别在于覆盖范围。稠密索引通常为每条被索引的记录或每个不同的搜索键值设置一个条目,并提供查找所有匹配记录的方法。稀疏索引只记录选定的边界,例如每个数据页记录一个键。稀疏索引通常依赖底层数据的有序性:边界用于确定接下来必须搜索的区域。多层有序索引即使在叶节点中稠密地表示被索引的记录,也可以在上层采用稀疏结构。

索引不等同于数据备份或缓存。它通常作为数据库持久化状态的一部分加以维护,不过往往可以根据权威数据重建。索引也不同于物化视图,后者存储查询结果,其中可能包含连接或聚合。不过,两者之间的界限并非绝对:覆盖索引会存储选定的行值,而某些数据库系统还实现了索引视图,其维护方式与索引类似。

有序树与范围访问

应用最广泛的通用数据库索引基于 B树家族。鲁道夫·拜尔和爱德华·麦克雷特于 1970 年提出 B树,相关期刊论文发表于 1972 年。B树的核心特性是高扇出:每个内部节点存储多个分隔键和子节点引用。通过使节点大小与存储页相匹配,这种结构减少了定位一条记录所需的页面访问次数。

B+树将数据条目存储在叶节点层,而将路由信息存储在内部节点中。叶节点通常按键的顺序相互连接,使系统只需沿树向下查找到范围的起点,之后便可沿相邻叶节点继续访问。这支持等值查找、不等值查询、有序遍历、最小值与最大值查找,以及某些形式的分组操作。产品文档常用“B树”泛指具有 B+树特征的结构。

对于 NN 个条目和有效扇出 ff,层数的增长近似满足

h≈log⁡fN.h \approx \log_f N.

如果一个内部节点可以将查找导向约 200 个子节点,那么仅经过几层就能定位十亿个条目中的任意一个,具体取决于叶节点容量和占用率。根节点及上层节点所在的页面通常会被缓存,因此一次查找产生的物理读取次数可能少于树的高度。因此,相关的计算复杂性既包含比较操作的成本,也包含存储访问的成本;只计算比较次数,可能会掩盖实际应用中的主要成本。

插入操作会先定位目标叶节点,再添加条目。如果页面空间不足,实现中可能会重新分配条目,或拆分页面,并在其父节点中加入一个分隔键。拆分可能向上传播,偶尔还会产生新的根节点。删除操作可能留下空闲空间、触发页面合并,或将空间回收推迟到以后进行。实际实现往往会放宽教科书中的占用率规则,以避免在并发操作期间进行代价高昂的结构调整。

页面布局对性能有显著影响。前缀压缩可以减少重复的键内容;当路由不需要完整键时,后缀截断则可以缩短内部节点的分隔键。可配置的填充因子可以为后续插入预留空间。顺序递增的键往往会使插入集中在最右侧的叶节点;随机键则会分散写入,但也可能导致更零散的页面访问和更多碎片。

有序索引的作用也不止于筛选。例如,建立在 (customer_id, order_date) 上的索引可以按时间顺序返回某位客户的订单,而无须另行排序。不过,只有当索引的比较规则与查询要求一致时,索引顺序才有用,这些规则包括排序方向、排序规则以及对空值的处理方式。叶节点中的条目在逻辑上有序,并不意味着页面在物理上一定相邻。

哈希索引与日志结构设计

哈希索引对搜索键应用哈希函数,并根据计算结果选择桶或目录项。它的概念基础是哈希表,但针对持久化存储、变长记录、并发和恢复等需求作了适配。当哈希函数能均匀分布键,且桶的占用率得到控制时,等值查找访问桶的期望时间可以是常数,不过哈希冲突和溢出页会增加额外开销。

哈希通常不保留键的顺序。因此,为 account_id = 417 设计的索引,并不会自然地有助于处理 account_id BETWEEN 400 AND 500 或按序输出。即使是等值查找,也可能需要比较原始值,因为不同的键可能具有相同的哈希值。如果数据中存在大量重复值,无论不同值的分布多么均匀,大量索引项仍可能集中在同一个桶中。

动态哈希能够适应数据增长,而不必在每次扩容后都进行全面重组。可扩展哈希使用由选定哈希位寻址的目录,并按需分裂桶。线性哈希则按照受控的桶分裂顺序扩容,逐步改变哈希空间中哪些部分使用更大的桶地址范围。这些技术在目录开销、分裂方式和溢出管理之间采取了不同的权衡。它们的实际价值取决于等值访问带来的收益,是否超过有序索引所具备的更广泛功能的价值。

日志结构合并树,简称 LSM 树,采用另一种方法来平衡读写。帕特里克·奥尼尔及其同事于 1996 年描述了这种结构:它先在内存组件中积累更新,再定期将有序数据段写入存储。后台压实会合并这些有序段、重新组织键,并在旧版本不再需要时将其丢弃。LSM 设计广泛用于持久化键值存储引擎,而这些引擎又可用于实现数据库的主索引和二级索引。

LSM 查找可能需要检查多个组件,而不是只沿一条树路径查找。布隆过滤器可以排除确定不包含目标键的有序段,从而减少不必要的读取。布隆过滤器可能产生假阳性,但只要构建和维护正确,对于其中所表示的键就不会产生假阴性。范围查询会合并相关有序段的有序迭代器,并处理同一键的多个版本。

LSM 设计通常从读放大、写放大和空间放大三个方面来解释。压实会重写数据,使实际写入量超过原始更新量;有序段之间的重叠会增加查找工作量;多个版本则会在清理之前持续占用存储空间。分层压实和分级压实策略以不同方式平衡这些影响。因此,无论是“哈希索引具有常数时间复杂度”,还是“LSM 树针对写入进行了优化”,都不足以完整预测性能:工作负载的特征、内存分配、持久性设置和后台维护仍然具有决定性作用。

面向分析和复杂数据的专用索引

有些查询谓词无法用单一的、从标量值到数据行的有序映射来处理。位图索引使用位向量表示某个值或条件,其中各位指示哪些行满足该条件。布尔运算可以高效地组合这些向量:分析查询可以先对区域、产品类别和时间段对应的位图求交集,再读取符合条件的行。当位模式具有适当的结构时,压缩可以降低这种表示方式的存储开销。

位图索引尤其常见于以读取为主的分析型工作负载和数据仓库。低基数属性是其常见应用场景,但经过压缩和编码的位图方案也能支持基数较高的属性。更新特征与基数同样重要:并发修改大量行可能产生维护或锁定开销,使某些位图实现不适用于事务密集型表。查询执行器临时构建的位图不应与持久化的位图索引混为一谈。

倒排索引将词项或特征映射到包含它们的对象。其基本组成包括词项字典,以及每个词项对应的倒排列表。面向文本的倒排记录可以包含文档标识符、词项频率和词元位置。位置信息支持短语查询求值,频率信息则用于相关性评分。这种结构将数据库索引与信息检索联系起来,也适用于数组、标签以及包含多个值的文档字段。

空间索引表示的是位置和空间范围,而不只是标量的顺序。安东宁·古特曼于 1984 年提出的R树通过包围矩形对对象分组。查询首先找出可能与所查询区域相交的矩形,再在必要时检验实际的几何对象。包围区域之间的重叠可能导致查询需要遍历多个分支,因此性能取决于空间分布和对象的组织方式。包围盒匹配通常只意味着候选匹配,并不能证明精确的空间谓词成立。

与逐条记录建立索引相比,块级摘要提供了一种体积小得多的替代方案。每个块的最小值和最大值可用于排除取值范围不可能满足谓词的块。PostgreSQL 的块范围索引(BRIN 索引)为一段连续的物理页保存摘要;分析系统中也有相关的“区域映射”(zone map)技术。当某一列(如事件时间)与物理存储顺序相关时,这类结构尤其有效。如果几乎每个块都覆盖完整的取值范围,它们就难以发挥数据跳过的作用。

向量索引支持对数值嵌入向量进行相似性搜索。相关技术包括基于图的搜索、倒排分区和量化。许多实现返回的是近似最近邻,以牺牲精确性来换取速度和内存效率。这与常规的等值索引有本质区别,后者旨在依据既定的比较规则找出所有符合条件的条目。将相似性排序与普通过滤条件结合,还会带来额外的查询规划问题,例如应在候选项生成之前、生成过程中,还是生成之后进行过滤。

复合键、表达式与覆盖访问

复合索引使用多个属性对索引条目进行排序或组织。在基于 (a, b, c) 的常规有序索引中,比较按字典序进行:先比较 a 的值,在 a 值相等时比较 b,然后再比较 c。因此,前导属性尤为重要。针对 a 的条件通常能确定一个连续区域,而仅针对 c 的条件所匹配的条目可能分散在整个索引结构中。

常见的“最左前缀”规则描述的就是这种组织方式,但它并不是对所有优化器行为的绝对断言。有些系统会执行跳跃扫描、针对不同的前导列值反复探查,或组合使用多个索引。对前导列施加等值约束,通常可以让后续的范围约束确定一个较窄的区间。如果较早的列上存在范围条件,后续列对该区间的限定作用可能会减弱,不过,在读取表中的行之前,仍然可以利用后续条件过滤索引条目。

例如,假设有一张订单表,并在 (customer_id, order_date) 上建立了索引。以下查询:

SELECT order_date, total
FROM orders
WHERE customer_id = 42
  AND order_date >= DATE '2024-01-01'
ORDER BY order_date;

可以利用客户标识符选定索引中的一部分,再利用日期条件确定扫描的起始位置。对于该客户,得到的索引条目已经按日期排列。将两列的顺序颠倒会形成不同的访问路径:它更有利于跨客户按日期访问数据,但通常无法同样直接地定位某一客户的记录。

覆盖索引包含某个特定查询所需的全部值。有些系统允许通过 INCLUDE 子句加入非键列,从而区分承载的数据与用于排序的属性。这可以避免读取完整记录,但能否实现“仅索引”访问取决于具体实现。在某些可见性机制下,除非辅助信息能够确认索引所指向的行对当前事务可见,否则执行器仍须访问表存储。更宽的索引也会占用更多页面,并增加维护工作量。

表达式索引存储计算结果,例如规范化后的电子邮件地址,或从时间戳中提取的日期。它是否有用,取决于系统能否识别出查询中的表达式与建立索引时使用的表达式相匹配。表达式的行为必须足够稳定,才能保证已存储的索引条目持续有效;因此,各种数据库产品都会限制允许使用的函数。

部分索引在某些系统中也称为筛选索引,只包含满足某个谓词的行。仅针对未处理任务建立的索引,可能比覆盖全表的索引小得多。优化器必须先确认查询条件在逻辑上蕴含索引谓词,才能使用该索引。唯一部分索引可以强制选定子集内的值保持唯一。至于唯一性的判定,则遵循各产品对空值、排序规则和比较方式的具体规定,而不是依据某种通用的文本相等定义。

查询规划、选择率与成本

存在索引并不意味着使用索引就是成本最低的执行策略。查询优化器会在整体执行计划中比较各种可能的访问路径,而该计划还可能涉及连接、排序、聚合和并行执行。当查询需要检索大量行时,表扫描可能比索引访问更快,尤其是在索引查找会导致分散读取,而扫描能够按顺序处理数据页的情况下。

选择率指满足某个条件的行所占的比例,不过在讨论谓词和键值的互异程度时,术语的用法偶有差异。如果一张表包含 NN 行,且估计某个谓词能匹配其中比例为 ss 的行,那么预计符合条件的行数为

M^=sN.\widehat{M}=sN.

索引访问路径的成本不仅取决于 M^\widehat{M},还取决于包含这些行的数据页的数量及其分布。一万条匹配记录若紧密聚集在几百个数据页中,其读取成本可能低于分散在一万个数据页中的同等数量记录。

优化器会根据行数、不同值的数量、常见值的频率、直方图,以及数据值与物理排列顺序的相关性等统计信息来估计基数。组合谓词尤其难以估计。如果城市与邮政编码高度相关,在假设二者相互独立的前提下将各自的选择率相乘,就可能严重低估匹配行数。扩展统计信息或多列统计信息能够反映其中一些关系,但无法消除估计误差。

一种简化的比较方法是将索引遍历、索引条目处理和行检索的成本分开计算:

Cindex≈Cdescent+Centries+Cfetch,Cscan≈P cpage,C_{\text{index}} \approx C_{\text{descent}} + C_{\text{entries}} + C_{\text{fetch}}, \qquad C_{\text{scan}} \approx P\,c_{\text{page}},

其中,PP 是表的数据页数量,cpagec_{\text{page}} 是估计的每页扫描成本。实际模型还会考虑缓存效应、处理器运算开销、预取、并行性和存储设备特性。不存在一个通用的匹配行比例阈值,能保证低于该阈值时使用索引就一定有利。

谓词的形式会影响可用的访问路径。对于 price * 1.2 > 120 这样的条件,直接利用 price 上的普通索引,可能不如利用优化器能够识别的等价范围条件容易。隐式类型转换、排序规则不匹配,以及对索引列应用函数,也可能妨碍索引访问。反过来,优化器有时也能改写表达式或推导取值边界,因此不能仅凭语法形式判断是否会使用索引。

索引不仅影响单独的筛选操作,也会影响连接。索引嵌套循环连接使用外部关系中的值,反复在内部关系上进行索引查找;当外部输入较小且每次查找的选择率较低时,这种方式可以很高效。对于较大的输入,哈希连接或归并连接的成本可能更低。1979 年针对 System R 开展的访问路径选择研究,确立了对基于成本的关系查询规划具有深远影响的方法,其中包括综合考虑访问方法和连接顺序。

事务正确性与并发访问

索引必须符合数据库的事务规则,而不能仅仅与存储介质上可见的最新值保持一致。插入、删除或更新一行数据可能影响多个索引;发生故障后,不能让已提交的行无法通过本应包含它的索引访问。因此,索引维护需要与事务提交、恢复和隔离机制相结合,而不能被视为一项独立的优化措施。

预写日志会在相应的数据页持久化之前,记录恢复变更所需的信息。恢复过程可以重放已提交的结构变更,并按照引擎的设计处理未完成的操作。索引页分裂尤其需要谨慎处理:如果在移动条目与设置路由信息之间发生崩溃,不能因此导致某些键永久无法访问。不同系统会根据自身的恢复架构,记录物理变更、逻辑操作,或将两者结合起来。

并发控制区分两类保护:对内存结构的短期保护,以及对逻辑数据的事务级保护。读取或修改树节点时,可以用页闩锁来保护该节点;而锁则可以保护某个键或键范围,直到事务到达适当的边界。这些机制的用途不同:持有事务锁,本身并不意味着可以安全地并发修改内存中的页面。

在多版本并发控制机制下,一个逻辑行的多个版本可以同时存在。索引可能包含指向某些版本的引用,而这些版本对特定快照并不可见,因此需要额外检查。更新之后,旧条目并不总能立即回收,因为较早开始的事务可能仍然需要它们。待可见性规则允许时,清理、垃圾回收或压实操作最终会移除这些过时状态。

唯一性检查必须考虑并发操作。两个事务插入同一个要求唯一的值时,不能仅仅因为它们最初都未看到对方尚未提交的行,就允许两者都提交。引擎必须通过锁、冲突检测、等待或验证等方式进行协调。同样,可串行化执行可能需要保护所查询范围内“没有记录”这一状态。否则,另一个事务就可能插入新的匹配行,产生幻影行,使第一个事务据以执行的假设不再成立。

在线索引构建还会带来另一类一致性问题。索引构建程序扫描现有数据时,并发事务仍在持续修改表。正确的协议必须协调扫描结果与这些变更,并确立一个时间点,使构建完成的索引从此可以有效地用于普通查询。实现时通常会结合使用快照、变更捕获、多轮处理、验证以及短暂的同步阶段。因此,“在线”或“并发”构建并不一定意味着完全不加锁,也不意味着在整个构建过程中所有操作都不受影响。

构建、维护与工作负载设计

为已有表创建索引时,批量构建通常比逐条执行普通插入更高效。一种常见方法是提取键与行标识符的配对,将其排序,然后依次构建叶子页和内部页。当索引条目超出可用内存容量时,外部排序会先生成多个有序段,再利用临时存储将其归并。并行提取和排序可以缩短构建时间,但存储带宽以及索引最终的组织方式仍然是制约因素。

每增加一个索引,都会增加写入成本。插入操作通常需要向所有适用的索引添加条目;删除操作使相应条目可以被移除;更新操作则可能需要删除旧键并插入新键。修改未建立索引的列时,有时可以借助存储引擎特有的优化来避免索引操作。反过来,如果索引存储了许多包含列,即便搜索键列没有变化,也可能需要维护索引。

存储成本并不只是被索引值的大小。索引条目还包含行引用、头部信息、对齐开销,有时还包含可见性或版本信息。内部页、页内未使用的空间以及保留的过时条目也会带来额外开销。如果二级索引的每个条目都存储一个较宽的主键,那么主键的选择就可能显著影响所有二级索引结构的总大小。

碎片化和膨胀有多种含义。页分裂可能留下未填满的页面;删除操作可能留下可复用的空间;过时版本可能仍在等待清理;键的逻辑顺序也可能与物理存放顺序不一致。重建可以使索引更紧凑,但也会消耗输入/输出带宽、临时空间和事务日志容量。如果工作负载本身就需要为随机插入预留空闲空间,那么刚压紧的结构可能很快再次扩张。因此,维护需求必须结合存储引擎来理解,而不能仅凭一个碎片率来判断。

索引选择是一个需要从整个工作负载层面考虑的问题。某种结构虽然能加速一条查询,却可能拖慢频繁执行的更新操作,占用另一个索引所需的内存,或大幅增加复制流量。高度相似的索引有时可以合并,但较长的复合索引并不总能替代较短的索引:它可能体积更大、缓存效率更低,或者其排序方式不符合另一条查询的需要。用于强制执行约束的索引,还承担着保障正确性的作用,这一作用独立于实测的查询使用情况。

性能评估需要区分预估执行计划与实际执行情况。检查执行计划可以了解索引扫描、行查找、剩余条件过滤和排序等操作,而运行时统计信息则能反映实际行数和页访问情况。测试必须考虑热缓存与冷缓存、参数分布、并发负载以及后台工作等因素。自动调优系统利用工作负载历史和假设性成本估算来提出索引调整建议,但其结论仍取决于它们观察到的工作负载和所采用的成本模型。

分区索引与分布式索引

分区将一张逻辑表划分为多个独立管理的子集,通常依据分区键的范围、所属列表或哈希值进行划分。局部索引覆盖单个分区,而全局索引跨越多个或全部分区。局部索引可以简化删除旧时间分区等操作,因为相应的索引数据可以随分区一同删除。全局索引可以支持通过非分区键直接访问数据,但在分区发生变化时需要额外的协调。

分区裁剪与索引解决的是相互关联但又不同的问题。分区裁剪识别出不可能包含相关行的分区;索引则在剩余数据中定位条目。针对分区键的查询可能无需使用索引,就能排除几乎所有分区。反过来,如果没有全局访问路径或路由信息,即使对另一列进行选择性很高的查找,也可能仍需搜索每个分区。

在分布式计算中,索引可以与其所描述的记录存放在一起,也可以独立分区。将索引与记录存放在一起可以简化本地更新和读取,但按二级键搜索时,可能需要访问许多分片。按全局二级索引自身的键对其独立分区,可以实现定向查找,然后再从保存基础记录的分片中获取记录。第二阶段会增加网络通信,并且可能需要跨越数据归属边界进行协调。

一致性对分布式二级索引尤为重要。如果基础行更新与索引更新在同一个分布式事务中完成,系统就可以提供强一致性保证,但代价是需要协调。如果索引采用异步维护方式,新插入的记录可能暂时不会出现在索引结果中,而已删除或已更改的记录则可能留下过时的候选项。获取并检查返回的基础行可以排除部分过时条目,却无法发现索引条目尚未到达的新行。

分片也会改变键值分布所带来的影响。单调递增的时间戳或标识符可能使写入集中在最新的范围分区,或分布式有序索引的最右端。哈希分区可以使写入分布更均匀,但会牺牲范围扫描中相邻数据的存储局部性。分区拆分、复合分区键和受控键前缀等技术,可以在数据分布的均衡性与查询必须访问的分区数量之间取得平衡。

分布式索引查询经常需要合并多个节点的结果。带有结果数量限制的有序查询可以请求各节点提供本地候选结果,再将其合并;聚合运算则可以在靠近存储的位置先完成部分计算。快照一致性要求参与查询的节点以一致的方式判定数据可见性。在重新分区和副本迁移过程中,即使数据位置发生变化,也必须保证路由的正确性。这些问题说明,分布式索引并不仅仅是存放在多台机器上的传统索引:它的访问路径还包含网络路由、故障处理和协调协议。

历史发展与持续研究

数据库索引源于关系数据库出现之前的文件访问方法。顺序文件、排序文件和索引顺序文件组织,在高效批处理与直接记录查找之间取得平衡。早期系统往往更直接地向程序员暴露物理访问路径。关系模型将逻辑查询与存储组织分离,使系统自主选择索引变得日益重要,而不再要求应用程序指定确切的访问顺序。

1970 年提出的 B 树,为动态维护有序存储提供了一个经久不衰的框架。20 世纪 70 年代,关系数据库原型系统展示了如何在声明式查询处理中选择索引。Patricia Selinger 及其同事于 1979 年发表的 System R 论文,使基于成本的访问路径选择成为数据库工程的基础组成部分。后续研究进一步丰富了索引方法:1984 年提出的 R 树用于处理空间对象,1996 年提出的 LSM 树则将面向更新密集型存储的合并式方法系统化。

硬件的变化一再改变索引操作之间的相对成本。在旋转磁盘上,减少随机寻道是首要目标之一。固态存储降低了机械延迟,但读取、写入和大规模顺序传输之间仍存在显著差异。内存数据库则让研究者更加关注处理器分支、缓存未命中、同步和内存分配。即便树的层数很少,如果每一层都需要在存储层次结构中进行难以预测的内存访问,其开销仍可能很高。

因此,压缩既是节省空间的技术,也是提升执行效率的技术。较小的键使每页能够容纳更多条目,并可提高数据驻留缓存的比例;压缩位图则允许一次操作处理大量行标记。面向分析的列式系统通常结合使用字典、排序数据段、数据块摘要和延迟物化,而非依赖某一种传统的行式索引。当编码后的表示能够直接支持谓词求值时,存储编码与索引之间的界限就可能变得模糊。

学习型索引探索利用机器学习模型预测键在有序数据中的位置,Tim Kraska 及其同事于 2018 年发表的研究是这一方向的重要代表。模型先估计键的位置,再通过有界搜索或其他受控搜索确定正确结果。这类设计并未消除对正确性保障机制的需求。更新、分布变化、预测误差、模型存储和重新训练的成本,都会影响它们能否优于经过精心设计的传统结构。

其他研究方向包括随查询到来而重组数据的自适应索引、自动化物理设计、注重缓存效率并减少轻量级锁使用的树结构,以及同时支持结构化谓词与相似性搜索的索引。比较评估仍然困难,因为一种索引在某种键分布或读写比例下可能表现更好,在另一种情况下却可能表现更差。相关评估指标不仅包括单独执行查找时的速度,还包括尾延迟、持续更新吞吐量、恢复时间、存储放大,以及维护操作进行期间的性能。