二叉排序树是 由树到索引(4)

2.当Leaf Page满，Index Page未满时候，首先拆分Leaf Page,将中间结点放入到Inde Page中，然后小于中间节点的放左边，大于或者等于中间结点的放右边；

再次插入70这个值的时候，Leaf Page已经满，但是Index Page还没满，在根节点插入叶子节点中间结点，然后在进行页分裂；

3.当Leaf Page和Index Page都满的时候，首先拆分Leaf Page，小于中间结点的记录放左边，大于或者等于中间结点的记录放右边，接下来拆分Index Page,相当于提升整颗树的高度，小于中间结点的放入到左边，大于或者等于中间结点的放入到右边，最后讲中间节点放入到上一层Index Page；

接下来插入95，这个时候Leaf Page和Index Page都满值，没办法插入，这个时候就需要进行2次拆分，首先拆分叶子结点，最后在拆分根结点。二叉排序树是

以上图2和3都没有添加双向链表，主要是为让大家看明白分裂的情况。

删除操作:

B+树使用填充因子来控制树的删除删除变化，50%是填充因子可设置的最小的值，小于这个值这个时候就需要做合并操作，删除操作同时也必须保证删除后的结点依然排序。

1.Leaf Page和Index Page都大于填充因子，如果删除的是叶子节点直接删除就好，如果删除的是Index Page的元素，使用该结点的右结点代替；

如上图删除70这个节点，直接删除就可以了

2.Leaf Page小于填充因子，Index Page大于填充因子，这个时候合并叶子节点和他的兄弟节点，更新Index Page；

接下来删除25，在这个时候满足第一种情况，但是这个值又在Index Page中，删除25以后，还需要将右兄弟替换到Page Index中。

3.Leaf Page和Index Page都小于填充因子，这个时候需要叶子节点做合并，当删除掉Index Page结点以后Index Page也需要做合并。

接下来我们删除60，这个时候删除60以后Leaf Page不满足填充因子，进行合并，同时删除Index Page的值也需要做合并。

B+树索引的本质就是B+树在中的实现，B+树在中的高度一般为2-4层，这个怎么实现的我们先不要去管，但是我们要知道这样做就会导致我们查询速度很快，高度为2-4层意味着我们查找一个数据所需要做的IO操作为2-4次，磁盘每秒可以做100次的IO操作，这就意味着我们能在0.02-0.04秒查找出数据。是不是很快。中分为聚集索引和非聚集索引，这两者的差别在于叶子节点是否存在一整行数据。

聚集索引：

这里思考一个问题，我们在建表的时候会建立一个主键，这是为什么？其实这个主键就是我们的聚集索引，要是不建立主键，那么我们存储的数据就会在无序的存在磁盘中，当然查询会慢，但是建立主键以后，中的数据会按照B+树的特点进行构建，整个表变成一个索引，叶子节点存放的是表中的整行数据，这就是我们所说的聚集索引，非叶子节点的索引存放的是键值以及数据页的偏移量。聚集索引的好处在于，对于主键查找的和排序非常快，因为叶子节点存放的就是我们的数据，另外每个叶子节点之间的连接都是双向链表，不需要再一次进行查找。

非聚集索引：

非聚集索引的叶子节点并不包含所有行的数据，叶子节点除了包含键值以外，每个叶子节点的索引包含一个书签，用来保存相对应的行数据的聚集索引的键。所以当通过非聚集索引查询数据的时候，首先会遍历非聚集索引并通过叶子节点的指针获得指向聚集索引的键，然后通过聚集索引查找与之匹配的叶子节点。每次给表中增加一个非聚集索引，表中的字段就会被复制出来一份，生成索引，所以给表添加索引就会增加表空间，减慢插入时候的速度。

联合索引：

联合索引就是在表上的多个列建立索引，联合索引本质上还是一棵B+树，不同的是联合索引的键值数量不是1，而是大于等于2。二叉排序树是为什么需要联合索引的存在？

1.假设(a,b)列建立索引，对于查询条件而言，当查询的条件为a和b,则可以使用，条件单独为a的时候也可以使用，但是为b的情况不可以使用；

2.对于(a,b)列建立的索引，第二个列是排序的，这样当我们按照b条件排序的时候就不需要进行排序操作；

明白了索引的原理我想大家以后在优化查询的时候也有清晰的思路了吧，以上是B-Tree索引介绍，另外Hash索引我们以后再聊。

四、结束语

主要参考《大话数据结构》和《MySQL技术内幕：InnoDB存储引擎》

提前祝福大家新年快乐！今天是我的最后工作日了~可以回家看望父母了！另外有什么不懂可以进群咨询438836709~

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-68999-4.html