B树和B+树的区别

喜欢ヅ旅行 2022-11-19 09:54 196阅读 0赞

因为我们要考虑磁盘IO的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，它的每个节点最多包含m个孩子，m称为b树的阶，m的大小取决于磁盘页的大小

## B树 ##

另一个名字就是二叉树索引。  
1.每个节点的儿子节点都是两个，左边是比该节点小的，右边是比该节点大的，这两个索引的儿子节点同样是这种情况  
2.所有的节点都是一个关键字

![20210121002722403.png][]

搜索的时候是从根节点开始搜索的。  
比如搜索的是35，则直接命中。如果搜索“28“，那就是比35小，左边节点，“17”，“28”比“17”大，则右边节点，直到命中

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MDQyOTM4_size_16_color_FFFFFF_t_70][]

## B+树 ##

我们把所有的数据进行折半块查找，比如一共100条数据。在30和60的地方分一下，存放30和60的节点就是根节点。30和60就是该节点的关键字，100也就是分成了3份，这个节点自动创建三个指针。这三份就是根节点的子节点，**（敲黑板划重点，子节点的个数=关键字个数+1，没有子节点就不说了）**。下面继续分，拿其中一个子节点举例，把30分成3分，10和20当成关键字，下面继续是三个子节点。。。依次类推

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MDQyOTM4_size_16_color_FFFFFF_t_70 1][]

在每一个叶子节点做一个标记，把这些标记存起来，每次查的时候可以在查询根节点的时候从叶子节点也开始查，这样是不是就省了好多时间呢。  
而这些标记就是**链指针**。把这些链指针存进一张表中,这个表就是**稠密索引**.

[20210121002722403.png]: /images/20221119/b99aa3c91b9a4c0ba54eb4f635ba44f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MDQyOTM4_size_16_color_FFFFFF_t_70]: /images/20221119/cef4743c5e8049b5a50b169e761f30ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MDQyOTM4_size_16_color_FFFFFF_t_70 1]: /images/20221119/f8443eac697945399112bc39c1461f96.png