CMU15445 Lecture 7 & 8 Tree Indexes

回顾

上节提及了许多数据库内部使用的数据结构，它们可以用来存储内部元数据，存储核心数据，临时数据结构，实现表的索引，表的索引，可能涉及范围查询

表的索引（Table Indexes）

定义

table index是表的某些列（某些attribute）的一个复制，并包括一个指向某些tuple的标识，比如主键，或者指向tuple的指针。这些索引一般按复制的attribute被排序了。DBMS可以通过这些索引高效的找到对应的tuple，并且需要保证table与index的对应内容逻辑上是一致的。

这里存在一种权衡，如果建立的索引较多，那么取数据也更快，但是需要更多的内存以及更高的维护成本，DBMS需要决定最好的索引以执行最优的查询

B+Tree

定义

B+Tree是一种自平衡树，它可以使得内部数据有序，并且支持在O(logn)的时间完成查找，线性访问，插入，删除操作。它是** disk-oriented DBMS’s**用来针对读写大量数据的一种优化

B树与B+树的区别

B树并不支持线性遍历，因为其会将所有的key/value存在所有的节点中，而B+树对于非叶子节点存的是下一层孩子的地址与key，只有叶子节点才存key/value对。对于DBMS而言，B+树索引的键值分别表中某些列(某些attribute)的一个复制与是指向某些tuple的标识

每一个B+树的node(可以存很多个数据)，一般会按照key排好序

B+树的结构

一颗M路B+树得满足以下条件：

• 它必须得是完全自平衡的，也就是说每个叶子阶段

一些问题

• 就是节点的层数level，
• hash表有个缺点，就是其天然不分块，17：10，如需要将hash表放到硬盘，需要考虑如何将hash表分块，而b+树可以一个叶节点占一个页,假定HASH表项与B+树叶节点的数据大小一致，当一个B+树节点能够正好放满一个页，这时候HASH的表的表项大概率不会放到一个页中