B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。

首先，对单个节点来说，是一个key value结构，key是作引的列，value有两种，对于聚簇索引来说，value就是数据，对于二级索引来说，value就是指向数据的地址。

B-Tree的结构如下：

B-tree的特点是非叶子节点上也有数据。

B+Tree是B-Tree的变体，它的结构如下：

非叶子节点的职责就是为了定位下级节点的区间，不需要存储数据。数据全部分散在叶子结点上。

B+Tree索引的优势：

由于非叶子节点不存放数据，所以可以将非叶子节点定义为固定的区间，然后可以设计每个区间的叶子结点都存放在一片固定大小的连续的内存区域，在读取的时候可以避免出现硬盘大量随机读的现象 。

Mysql中，不论是MyISAM还是InnoDB，都是使用的B+树索引，不过InnoDB使用了聚簇索引，所以索引文件和数据文件是放在一块的。MyISAM中，索引文件和数据文件是可以分开的。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字 段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为 InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用 自增字段作为主键则是一个很好的选择

ORACLE的索引是B-tree索引。

Mysql和ORACLE索引的实现方式