数据结构（十一）B树

我不是女神ヾ 2021-09-20 09:38 354阅读 0赞

之前的二叉排序树，平衡二叉树都是基于二叉树的实现，但是在搜索过程中，效率和树的深度有关，所以就想到把二叉树改为多叉树，B树和B+树都基于多叉树的实现

# 多路查找树 #

![4387][]

# B树 #

## 定义 ##

![4389][]

![4391][]

## 应用场景 ##

![4393][]

# B+树 #

涉及到遍历的场景，B树就有明显缺陷了，需要类似树的中序遍历，而这样的IO开销是很大的，从而就引出了B+树

## 定义 ##

![4423][]

也就是说，真正的数据存在叶子结点，其它结点存放的都是叶子结点的索引

随机查询则从根结点开始遍历，顺序查询则可以从最左侧的叶子结点遍历

## 应用场景 ##

![4434][]

# 数据库数据结构 #

大多数数据库，如mysql，底层的数据结构也是采用B+树来实现

1.树的深度会很大影响搜索效率，每多一层，就多一次IO，所以一般而言树深度越小越好，而B树/B+树支持多阶，符合要求

2.数据量大了，就会出现索引，索引多了也会占据存储空间，B+树只在叶子结点存储真实数据，其它结点存储索引，可以提高索引结点的空间利用率

3.结合磁盘特点，磁盘寻找数据需要经历三个时间， **寻道时间**， **旋转时间**， **传送时间**，而其中寻道时间消耗的时间最长。磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数。所以一般数据库中的B+树采用与盘块大小相同的阶数。

**盘块**：也就是扇区，一般是连续的512字节

**寻道时间**：磁头找到对应的磁道

**旋转时间**：在磁道上通过旋转找到对应的数据

**传送时间**：通过计算机总线加载到内存

# 参考资料 #

从磁盘的使用角度来说明数据结构的应用场景

[http://blog.csdn.net/v\_july\_v/article/details/6530142][http_blog.csdn.net_v_july_v_article_details_6530142]

[http://www.cnblogs.com/yangecnu/p/3632027.html][http_www.cnblogs.com_yangecnu_p_3632027.html]

//B+树和在数据库innodb的应用

[http://www.ruzuojun.com/topic/420.html][http_www.ruzuojun.com_topic_420.html]

转载于:https://www.cnblogs.com/ulysses-you/p/7153717.html

[4387]: /images/20210726/654ee1e266a74318b4f5abb8b11ab37e.png
[4389]: /images/20210726/5bbd691a11b7413cab3f363b819654f2.png
[4391]: /images/20210726/5a0cc9f237ff414fba2835b3f759e9d0.png
[4393]: /images/20210726/9178d8bf410f49508da9eb082337a798.png
[4423]: /images/20210726/8cf1795a5f7e47ea9a0637b0bec58bb1.png
[4434]: /images/20210726/2a322b1aefb54bdcbca8a12310f1bceb.png
[http_blog.csdn.net_v_july_v_article_details_6530142]: http://blog.csdn.net/v_july_v/article/details/6530142
[http_www.cnblogs.com_yangecnu_p_3632027.html]: http://www.cnblogs.com/yangecnu/p/3632027.html
[http_www.ruzuojun.com_topic_420.html]: http://www.ruzuojun.com/topic/420.html