数据库索引从二叉树到B-树再到B+树的演变_二叉平衡树到b树的演变过程

    索引是数据库学习过程中必不可少的话题，也是一个尤为重要的概念，索引包括B-树，B+树，Hash树等等，但本文重点讨论B-树和B+树。

1 索引的作用

    索引：在数据表的一个或多个字段上创建的一种数据结构，帮助数据库高效的获取数据。

1.1索引的优势？

1.为表中被请求的数据行提供直接指针；
2.在一些情况下，避免排序操作；
3.避免了对基表所有数据页的访问，直接扫描全索引页和少量数据页。

1.2索引的缺点？

1.索引占物理和数据空间，以存储空间为代价减少I/O。
2.数据的删除、更新和插入操作中会带来额外的索引维护成本,而且索引越多成本越大。

2 索引的实现

    索引的实现和数据库存储引擎相关，不同数据库存储引擎采用的索引方式不同，如MySQL的InnoDB和MyISAM都采用B+ Tree实现，但存储细节上不一样。InnoDBInnoDB也支持hash索引。还有数据库采用堆栈索引等。下文主要讨论B树。

2.1二叉树

    二叉树是最简单的B树，但是二叉树是一种极不稳定的数据结构，根节点的值对树结构影响极大，下图说明两个最主要的问题，1.根节点选择36和9完全呈现出两种不同结构，树结构和链结构。2.即使是图左侧的树结构也是一种不平衡树，比如搜索9需要2次，搜索56需要3次。

二叉树的四大缺点：

1. 每个非叶子节点至多两个子树，每个节点存储一个关键字。
2. 树的搜索深度不一致，搜索稳定性不好，查询效率不稳定。
3. 同样的关键字集合，根节点的关键字选择不好，树的深度结构差异很大。
4. 为了让二叉树尽量保持平衡，延伸出“平衡二叉树”，即B树。

2.2B-树

    B-树也称为B树，即Balance的意思，是在二叉树的基础改进，让树的叶结点后保持同样的深度。
    定义：B-树是一种多路搜索树（并不是二叉的&#