共计 2254 个字符，预计需要花费 6 分钟才能阅读完成。
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。所以每次查询的数据不超过一个页，数据不翻页，有助于提高查询效率。
思考问题：我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它们的时间复杂度比二叉查找树还小吗？
答案当然不是，Ｂ树和Ｂ+树的出现是因为另外一个问题，那就是磁盘IO。磁盘IO的效率低，那么当大量的数据需要被加载到内存，只能逐一加载每个磁盘块的数据，一个磁盘块对应树的一个节点，而平衡二叉树的树深度太大，导致磁盘IO过于频繁。所以Ｂ树和Ｂ+树就诞生了。
减少磁盘IO，就要降低树的深度，所以Ｂ树和Ｂ+树的基本特性就是：
- 每个节点存储多个元素
- 采用多叉树的结构
- 体型上看，就是棵矮胖的树
1.2 什么是B-Tree？
B-Tree 是一种多路搜索树，但不是二叉树。
为了描述B-Tree，需要定义数数据库的一条记录为一个二元组 [key, data]，key为记录的键值，就是数据库表中的主键，所以key是唯一的，data是一行记录中除主键外的数据。
可以看出：
- 每个节点占用一个磁盘块的空间
- 每个节点上的键值都是以升序排序的
- 每个节点存储多个元素
- 非叶子节点存储键值和数据外，还存储了子节点的磁盘地址（指针）
- 叶子节点存储键值和数据
- 查找的复杂度为复杂度O(log n)，即以2为底n的对数
B+Tree
B+Tree是在B-Tree的基础上做的优化，使其更加适合外存储索引结构（更加矮胖了）。使用代表：Mysql的InnoDB存储引擎
上面提到了降低树的深度可以减少磁盘IO，提升效率。所以为了让节点存储更多的数据，B+Tree在B-Tree的数据结构上，做了调整，非叶子节点只存储key键值和叶子节点指针，这样能大大增加非叶子节点存储的key值数量，进而减少数的深度
B+Tree相对于B-Tree有几点不同：
- 非叶子节点只存储key键值信息，叶子节点的地址信息
- 所有叶子节点之间都有一个链指针，是一种链式环结构
- 数据记录全放在叶子节点
- B+Tree有两个指针，一个指向根节点，一个指向关键字最小的叶子节点
根据以上特性，B+Tree可以进行两种查询运算：
- 对于主键的范围查找和分页查找（因为叶子节点是链式结构）
- 从根节点开始，进行的随机查找
聚簇索引 & 辅助索引
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树作为索引，比较合适。
