您的位置:首页>>资讯中心>>学习园地

Hash 索引,B树 和B+树

  为什么不都用 Hash 索引而使用 B+树索引?

  索引查找过程中就要产生磁盘 I/O 消耗,主要看 IO 次数,和磁盘存取原理有关。 根据B-Tree 的定义,可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘。

  预读原理, 将一个节点的大小设为等于一个页,这样每个节点只需要一次 I/O 就可以完全载入 局部性原理与磁盘预读

  B 树和 B+树的区别

  1、树,每个节点都存储 key 和 data,所有节点组成这棵树,并且叶子节点指针为 nul,叶子结点不包含任何关键字信息。

  2、B+树,所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接,所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而 B 树的非终节点也包含需要查找的有效信息)

  B+比 B 树更适合实际应用中操作系统的文件索引和数据库索引?

  1.B+的磁盘读写代价更低

  B+的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。

  2.B+tree 的查询效率更加稳定

  由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。


上一篇: 职生选择之第二个决定性因素:钱途

下一篇: 职业选择之城市与行业