数据结构技术知识总结之二——BTree

二. BTree

2.1 B-Tree 与 B+Tree

B-Tree 是 2-3 树的一种变形，可以设置度数 M，每个节点上最多可以有 M 个值；根据硬盘读取时的预读原理，磁盘读取时每次从磁盘上预读 page 容量（一般为 1024 字节）的整数倍，所以对于硬盘来说，可以将度设为 1024，这样就硬盘文件的索引就建立完毕，形成了一个 B-Tree 结构；

B-Tree 与 B+Tree 的区别在于：

• 节点的不同
  • B-Tree 的子节点都是相同的。无论叶子节点还是非叶子结点，上面存储的数据都是索引 + 数据；
  • B+Tree 的叶子节点和非叶子结点存储内容不同，非叶子节点只存储索引信息，叶子节点之存储具体数据信息；
• 索引与数据分离
  • B-Tree 各节点的索引和数据是放在一起的；
  • B+Tree 的索引和数据分离开来，所以非叶子结点只占用了很小一部分的空间，大部分空间被存储数据信息的叶子节点占据；
• 数据结构
  • B-Tree 是一个比较单纯的树结构；所以 B-Tree 结构的同一个父节点的相邻叶子节点，在物理上很可能是相距很远的；
  • B+Tree 在 B-Tree 的基础树结构之上，在叶子节点之间添加了指针连接，使所有叶子节点形成了一个链表结构，提升了叶子节点的顺序读取效率。

2.2 B+Tree 的优势

为什么 B+Tree 更加适合数据库、文件系统的存取模型？首先需要了解两个概念：

1. 磁盘结构：磁盘的物理结构是若干个同心圆组成的，每个同心圆都叫做磁道，每个同心圆按照一定的角度切分即为扇区。磁盘读取数据的过程，首先从地址总线获取数据存储的物理地址位置，然后磁头转动到相应的磁道上，该过程称为寻道时间；然后磁盘转动，磁头相对移动到数据在磁道上的位置，即到达了数据所在地址，该过程称为旋转时间；
2. 局部性原理：一个数据被访问的时候，其周围相邻的数据通常也需要被使用到。这是一个定理。
3. 磁盘预读：磁盘顺序读取的效率很高，因为顺序读取在同一个磁道上的数据，所以不需要寻道时间，只需要少量的旋转时间即可。所以根据局部性原理，磁盘在读取一个数据的时候，往往会将该数据周围范围内的数据也一并读取，即磁盘预读。

所以 B+Tree 在文件管理和数据库存储方面的优势就体现出来了：

1. B-Tree, B+Tree 的查询、插入、删除的时间复杂度都是 logN 级别，相对足够高效；
2. B+Tree 相对于 B-Tree 多了叶子节点的链表结构，所以在顺序读取的效率上是远高于 B-Tree 的；这在磁盘预读原理之下，成为十分重要的优势；
3. 磁盘预读的大小一般为一个页 (Page) 的整数倍，所以在 B+Tree 中将节点的度设置为一个 Page 的大小，则每次新建一个节点时都会将磁盘预读的数据信息存储到一个叶子节点中，相应索引信息存储到非叶子结点中。

2.3 B+ 树索引和 Hash 索引的区别

Hash 索引和 Java 的 Hash 原理基本相同，属于数组 + 链表 / 数组 + 红黑树的搜索方法。但和 B+ 比较有较少优点，较多缺点：

• 优点：
  • 更加适合等值查找。Hash 查询的效率本来就是 O(1)，如果所有 key-value 的 Hash 值都不同，则 Hash 索引查询的效率应该远胜于 B+ Tree；
• 缺点：
  • 不适合范围查找。key-value 经过 Hash 的计算，就会变的不连续，在范围查找上没有丝毫用处；
  • 不适合模糊查找。即使用 “LIKE %…%” 的语句，本质上和不适合范围查找是一样的；
  • 不适合大量等值的情况。即大量重复键值的情况下，key-value 计算出来的 Hash 值相同，这时候相同 Hash 值的内容形成链表，极端情况下复杂度变为 O(n)；（Hash 碰撞问题）
  • 不支持多列联合索引的最左匹配规则