1.1.1. 为什么 MongoDB 索引选择B-树,而 Mysql 索引选择B+树¶
关联: 索引树
关系型数据库是如何存储的:
![https://img.zhaoweiguo.com/knowledge/images/dbs/normals/index_mysql1.png](https://img.zhaoweiguo.com/knowledge/images/dbs/normals/index_mysql1.png)
聚合型数据库存储模型:
![https://img.zhaoweiguo.com/knowledge/images/dbs/normals/index_mongo1.png](https://img.zhaoweiguo.com/knowledge/images/dbs/normals/index_mongo1.png)
bson 的格式表示如下:
// Customer
{
"id": 1,
"name": Tom,
"billingAddress": [{"city":"China"}]
}
// Orders
{
"id": 99,
"orderItem": [
"productId": 27,
"price": 100,
"productName": book
],
"shippingAddress": [{"city": "china"}],
"orderPayment": [
...
]
}
为什么 MongoDB 使用B-树:
MongoDB 是一种 nosql,也存储在磁盘上,被设计用在 数据模型简单,性能要求高的场合。
性能要求高,看看B/B+树的区别第一点:
B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。
而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)
为什么 Mysql 使用B+树:
Mysql 是一种关系型数据库,区间访问是常见的一种情况,而 B-树并不支持区间访问
而B+树由于数据全部存储在叶子节点,并且通过指针串在一起,这样就很容易的进行区间遍历甚至全部遍历。
B/B+树的区别第二点:
B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等
而B-树每个节点 key 和 data 在一起,则无法区间查找。