CMU-15-445笔记(六)

Duplicate Keys

• Append Record Id
  • 将tuple的record id作为key的一部分，从而保证每个键都是不同的
  • 
  • 
• Overflow Leaf Nodes
  • 叶子节点分裂，将duplicate key存在overflow leaf node中，类似于链表的存储方式
  • 

Implicit Indexes

数据库会给完整性约束创建对应的索引，但是对于引用约束（外键）来说不会

Partial Indexes

局部索引可以减少index本身的大小

Covering Indexes

覆盖索引，如果query所需要的数据都在index中，DBMS可以直接从index中获取查询结构，不用去获取tuple本身

Functional/Expression Indexes

可以建立通过计算得到值的index

CREATE INDEX idx_user_login 
          ON users (EXTRACT(dow FROM login));

Trie Index

Trie树存储了数据的前缀，相同的前缀一个路径

Trie Key Span

Span是key对应的进制编码
1-bit Span Trie是指的存储二进制的key，每个node的分支树就是2

horizontal compreesion

当为1-bit Span Trie的时候，可以不存储0，1，直接存储存储两个指针就可以，这样也可以隐式的来表示01。

vertical compreesion

当前路径如果确定了一个特定的key的时候，可以提前终止路径，这样可以减少存储量，这样的trie 树也可以称之为Radix或者Patricia Tree

红圈处被直接压缩了

Inverted Index

Inverted Index用来存储文字与数据的对应关系，Inverted Index又可以叫做 full-text search index，也可以叫做concordance