浅谈B树

b树索引

索引是我们经常挂在嘴边的一个词，很多的书本都给大家贯彻了一个信息就是索引会增加我们查询的速度，但是很少会有详细的对b树索引有所介绍，现在我们这篇文章简单的说一说数据库中的最常见的b树索引。

b树索引是一种平衡多叉树，之所以叫b树，所代表的就是平衡balance，平衡的意思就是叶子节点的深度都是一致的（之后会提到）。b树索引经常被引用到文件系统和数据库系统当中。

b树索引结构：

我们这里先熟悉一些概念：

根节点： 每个b树索引都有一个根节点，实际上就是整个架构当中最顶端的结构，其下为分支节点。

分支节点：其内容包括结构下的分支节点或者叶子节点。

叶子节点：叶子节点直接将数据指向数据行（逻辑上的，不是物理上的）。

我拙略的画一个图，希望能让大家理解一下：

属性介绍：

我们先查看一下这里的索引的结构：

根节点中记录了每个分支节点的最小值和分支节点的块地址，是整个树的开始节点。

分支节点：

分支节点记录了叶子节点或者是下一层分支节点的键值最小值和物理位置。其中索引都是升序顺序排列，默认是升序。 每个分支节点的块（页）都是由数据块大小以及索引的长度决定。

叶子节点：

b树的索引结构一定保证叶子节点都在同一层，也就是说从根节点到叶子节点都有相等的分支节点，这里就是b的意义。这里不得不提到一个词语是索引高度，索引高度的意思就是根节点到叶子节点所遍历的数据块的个数，索引高度每增加一层，也就意味着在遍历的时候多了一次I/O。

叶子节点也有两部分组成，前面是索引的键值，单列索引的话就是这个字段所在的值，如果是符合索引，这个值是一个组合值。后面的是数据行的rowid。

叶子节点是一个双向的链表，每一个叶子节点包含上一个和下一个节点的指针。

数据库操作会影响索引：

我们在很多的书和资料当中都会写到当对索引有操作的时候，会对索引有不同的影响，索引也因此会有自动维护的操作，我们现在简单分集中情况去说一下：

Insert：

当执行insert操作的时候，要插入的值会对应的落到叶子节点的位置。但是当一个叶子节点块（页）满的时候，这样就会发生块（页）的拆分，这时候可能就会问会从哪里拆分，注意，在进行叶子节点块（页）拆分的时候，我们会从该叶子节点的上层父节点拆分，如果上层父节点没有足够的空间，会再向上层拆分。有一种特殊的情况是，如果空间一直不够，直到到根，那么要对根进行拆分。

拆分的方法：

如果insert的值在叶子节点块（页）中的值是最大的，那么这个拆分方法就是把新值放到新块（页），旧值依旧在旧块（页）当中。

如果insert的值不是最大叶子节点块（页），那么拆分的时候就是“五五开”。

针对根拆除的时候和其他节点不太一样，根在拆除的时候将原来的根节点分解为分支节点，放在新的块（页）中，将新的信息放在之前的块（页）当中，目的是减少开销

update：

update的操作会导致树中的位置页跟着改变，新的update的值会插入到新的叶子节点的位置。

delete：

delete的时候会发生索引产生碎片，alter index index_name rebuild;

注意：

针对索引的一些事情我简单的提一下，其实索引的设计随着之间的发展有很多的误区，首先我们知道，索引的目的是为了增加查询数据的速度，就是为了优化，然而优化是为了将当前有限的硬件条件做到极致和充分的利用，我们在这段数据库的学习的道路当中，学习到一些有关索引的设计的规避的条件，大部分是在一种很早的硬件条件下去规定的所以我这里说一下，索引的设计没有绝对。我先说我看到的几个误区：

索引的高度不应该超过5层，这是因为在b树索引当中，只有根会留在内存中，每增加一层都会增加I/O，层数越多证明我们在遍历索引的时候I/O也会随之增加。但是在现在的硬件情况下，我们完全可以认为所有的非叶子节点都缓存到内存当中。

单表索引不要超过表中字段的一半，这个其实怎么说，在保证所有的sql语句都能流畅运行才是设计的底线，如果需要索引，就建索引。

不设定不稳定的列为索引，这个在普遍情况下是这样的，因为索引的update我们在上面说会有重新插入叶子节点，会有磁盘的压力，但是，如果数据库因为某个sql语句存在性能低下，不妨试一试在一个不稳定列上创建一个索引，带来的效果可能会比想象中的不一样。

THAT'S ALL

BY CUI PEACE！！！！