B-Tree

B-Tree就是BTree,B树。-为连接符,不是减号。使用代表:MongoDB

1.1 为什么需要B-Tree&B+Tree?磁盘块的概念?

B-Tree是为了磁盘等外存储设备设计的一种平衡查找树

系统从磁盘读取数据到内存时,是以磁盘块(block)为基本单位的,位于同一个磁盘的数据会被一次性读取出来。

InnoDB引擎中有页(page)的概念,页是其磁盘管理的最小单位。InnoDB默认的页大小为16KB,也可以设置参数innodb_page_size,改为4KB,8KB,16KB;

系统的一个磁盘块往往没有一个页的容量这么大,因为 InnoDB 每次申请磁盘空间都是以若干个地址连续磁盘来达到页的大小,比如16KB。所以每次查询的数据不超过一个页,数据不翻页,有助于提高查询效率。

思考问题:我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它们的时间复杂度比二叉查找树还小吗?

答案当然不是,B树和B+树的出现是因为另外一个问题,那就是磁盘IO。磁盘IO的效率低,那么当大量的数据需要被加载到内存,只能逐一加载每个磁盘块的数据,一个磁盘块对应树的一个节点,而平衡二叉树的树深度太大,导致磁盘IO过于频繁。所以B树和B+树就诞生了。

减少磁盘IO,就要降低树的深度,所以B树和B+树的基本特性就是:

  • 每个节点存储多个元素
  • 采用多叉树的结构
  • 体型上看,就是棵矮胖的树

1.2 什么是B-Tree?

B-Tree 是一种多路搜索树,但不是二叉树。

为了描述B-Tree,需要定义数数据库的一条记录为一个二元组 [key, data],key为记录的键值,就是数据库表中的主键,所以key是唯一的,data是一行记录中除主键外的数据。

B-Tree示意图

可以看出:

  • 每个节点占用一个磁盘块的空间
  • 每个节点上的键值都是以升序排序的
  • 每个节点存储多个元素
  • 非叶子节点存储键值和数据外,还存储了子节点的磁盘地址(指针)
  • 叶子节点存储键值和数据
  • 查找的复杂度为复杂度O(log n),即以2为底n的对数

B+Tree

B+Tree是在B-Tree的基础上做的优化,使其更加适合外存储索引结构(更加矮胖了)。使用代表:Mysql的InnoDB存储引擎

B+Tree示意图

上面提到了降低树的深度可以减少磁盘IO,提升效率。所以为了让节点存储更多的数据,B+Tree在B-Tree的数据结构上,做了调整,非叶子节点只存储key键值和叶子节点指针,这样能大大增加非叶子节点存储的key值数量,进而减少数的深度

B+Tree相对于B-Tree有几点不同:

  • 非叶子节点只存储key键值信息,叶子节点的地址信息
  • 所有叶子节点之间都有一个链指针,是一种链式环结构
  • 数据记录全放在叶子节点
  • B+Tree有两个指针,一个指向根节点,一个指向关键字最小的叶子节点

根据以上特性,B+Tree可以进行两种查询运算:

  1. 对于主键的范围查找和分页查找(因为叶子节点是链式结构)
  2. 从根节点开始,进行的随机查找

聚簇索引 & 辅助索引

B+Tree索引又可以分为聚簇索引(clustered index),也叫聚集索引和辅助索引(secondary index)

  • 聚簇索引的叶子节点存放整张表的行记录数据。
  • 辅助索引的叶子节点只存储相应数据的聚集索引键,就是主键。当通过辅助索引来查询数据时,InnoDB会遍历辅助索引找到主键,然后再通过主键找到聚簇索引中完整的行记录数据。

MongoDB的索引和Mysql的索引选择?

思考问题:为什么MongoDB的索引使用B-Tree,而Mysql默认的InnoDB索引使用的是B+Tree?

先说说Mysql,关系型数据库

在关系型数据库的设计上,通常都是采用多张表来表达实体间的关系。一对一,用一张表。一对多,用两张表,一方存放多方的主键ID。多对多,用三张表,整个中间表。

而再做关联查询时,基本离不开join操作,无外乎就是从一个表取一个数据,去另一个表中逐行匹配。而B+Tree的叶子节点有链式指针,能提高这种遍历查询的速度,并且每次查询的效率比较稳定。

再说说说MongoDB,典型的非关系型数据库。

作为非关系型的文档数据库,本身就不适用有复杂的关联查询的业务场景。在设计数据结构时,官方也是推荐尽量把要用到的字段都放在同一个文档里。

{
    "_id" : ObjectId("5e675444b520d9b8bf291de3"),
    "groups" : [ 
        {
            "groupId" : "1234567788999901",
            "name" : "标准版"
        },
        {
            "groupId" : "1234567788999901",
            "name" : "定制版"
        },  
    ]
}

如上设计,把groups的数据都放在同一个数组里,而不会拆成两个collection来存储,因为这个非关系型的数据库,如果要设计成关联的,那么还是用关系型数据库。

其实这也是一种解耦的思想,关系型数据设计相当于把很多表都耦合在一起了。

所以MongoDB的查询大部分业务场景都是只需要查询一次就能查到结果的,而这样使用B-Tree运气好一次查询就能查出来,不需要项关系型那样去遍历操作了。

db.class.find( { _id: ObjectId("5e675444b520d9b8bf291de3") } )

因此,由于关系型数据库和非关系型数据的设计方式上的不同。导致在关系型数据中,遍历操作比较常见,因此采用B+树作为索引,比较合适。而在非关系型数据库中,单一查询比较常见,因此采用B树作为索引,比较合适。