表的索引是什么?

表的一部分属性的副本

当然这个索引一般都是预排序的

但是要保证索引与原表数据是相同的

索引的作用就是加速操作

当然索引越多,操作就越快,同样维护操作就要越多,存储占用也更多

本节课内容:

• B+ tree overview
• use in a DBMS
• design choices
• optimizations

B树家族:

• b-tree,这个东西叫b树,不叫b减树
• B+Tree
• B*Tree
• B^link-Tree

B-tree中的b不是balanced

B+TREE是自平衡的树,时间常数是O(log n),搜索时间的增长是慢于搜索量的增长,而且支持线性遍历

一个节点不一定只有一个数据,由指针和数据组成节点,节点之间是数据

B+TREE的节点(node),存的时候要按顺序存入,当然node中的数据可以含有很多内容

v可以是id,也可以是tuple

所以从数据结构上面就能简单的看出来右模糊的搜索比左模糊要简单

当然插入是很复杂的,当插入时节点空间不足时,要创建新节点,当然在删除时还要合并,也可以不合并

当有相同节点处理方法有两种,一种是简单加,一种是外链一个碰撞的key

B+Tree 设计中的几个注意点:

• node size
• merge threshold 节点合并的阈值
• variable-length keys 变长的key
• intra-node search 节点内部搜索的问题

• node size

最好是文件大小一致或者整数倍

如果磁盘存取时间越长,那么节点大小就要尽量越大

• merge threshold

并不是所有的都是节点变成一半就要合并,因为合并是要进行许多维护的

• variable-length keys

  • 存指针
  • 让节点本身是变长的
  • padding 后面补空字节,

• intra-node search 找节点

  • linear 一个一个找(线性搜索)
  • binary 二分搜索
  • interpolation 推断(假设内部数据是平均分配的)

B+tree 优化

• prefix compression 前缀压缩,将相同前缀的放到同一个节点中,给一个标志位
• deduplication 删除冗余,就是将相同的键合并成同一个键,将原本数据做成链表连接起来
• bulk insert 按批插入,一次插入一个完整节点