跳到主要内容

第十三章 索引

简介​

索引工作期间数据都在内存中。在checkpoint时，会持久化到外部存储上。与基于磁盘的索引结构不同。 目前索引用于维护表的约束：not null，唯一索引和主键。索引查询还未做。

在表的单个列或多个列上建索引，来满足某种约束。可以建多个索引。实质上是索引列的数据组织成索引键记录在索引结构中。 索引涉及到多方面：

  • 索引键和值。索引列数据的序列化方法。
  • 索引存储结构。用B+树，ART
  • 数据插入索引
  • 从索引删除数据
  • 索引序列化和反序列化。

索引应用的具体场景：

  • 事务临时存储需要索引维护表的约束。在事务未提交时，数据是插入在临时存储中的。
  • 表对象。事务提交时，事务临时存储的数据最终需要插入表对象。表对象需要用索引维护约束。
  • 删除数据。也要从索引删除数据。

索引结构​

索引键：索引列的数据序列化成字节串。 索引值：rowid

索引存储结构：用开源内存版本B+树。

索引结构关键信息：

  • 约束类型。唯一，主键等
  • 索引列信息。类型。
  • B+树
  • 列数据的序列化/反序列化方法。
type IndexKey struct {  
    _data unsafe.Pointer  //索引键
    _len  uint32  
    _val  uint64  //索引值。rowid
}

type Index struct {  
    _columnIds             []IdxType  //索引列
    _types                 []common.PhyType  //索引数据类型
    _logicalTypes          []common.LType  //索引数据类型
    _constraintType        uint8  //约束类型
    _btree   *btree.BTreeG[*IndexKey]  //B+树
}

插入数据​

  • 事务未提交时，数据进入临时存储。数据插入索引。用索引维持约束。
  • 事务提交时，数据从临时存储进入表对象，依然要插入表对象的索引。用索引维持约束。

数据按chunk进入索引。

分几步：

  • 构建索引键。索引列数据的序列化。
  • 插入B+
  • 插入失败后，已经插入的数据需要删除掉。

序列化方法：按chunk批量序列化。第一个索引列所有行序列化，然后第二个索引列所有行序列化，并与第一列序列化结果拼接起来。如此，知道全部索引列都拼接好。

删除数据​

  • 构建索引键。与插入时，索引列数据的序列化完成相同。
  • 从B+树删除索引键。

查询数据​

索引查询暂时未支持。

序列化和反序列化​

在checkpoint时，对索引序列化。存储引擎加载时，索引反序列化。 与上面的索引列数据序列化成索引键不同。

遍历每个索引，索引中的每个值序列化到磁盘上。反序列化，从block中反序列化出所有数据重新构建索引结构。

小结​

聚焦在索引结构的整体应用。未细讲B+树是如何设计的。索引查询还未实现也没讲。