数据结构 MySQL索引结构B+树

数据结构图示例网站：Data Structure Visualization

索引数据结构：

        二叉树

        红黑树

        Hash表

        B-Tree

B-Tree，特点：（每个节点都存储key和data，叶子节点指针为null）

        1、叶节点具有相同的深度，叶节点的指针为空

        2、所有索引元素不重复

        3、节点中的数据索引从左到右递增排列

如下图：

 B+树，特点：只有叶子节点存储data，非叶子节点的数据是冗余的，叶子节点包含了所有数据，叶子节之间有指针指向相邻叶子节点

        1、非叶子节点不存储data，只存储索引（冗余），可以放更多的索引

        2、叶子节点包含所有索引字段

        3、叶子节点用指针连接，提高区间访问的性能

如下图：

hash结构：

        1、对索引的key进行一次hash计算即可定位出数据存储的位置，很多时候效率高于B+树

        2、仅能满足=、IN，不支持范围查询

        3、hash冲突问题

 聚集索引和非聚集索引：

        非聚集索引，如MyISAM，索引文件和数据文件是分离的，分开存放；

        聚集索引，如InnoDB，索引文件和数据文件是一起存放的；

区别：

聚集索引非聚集索引一个表有几个只能有一个（包含了数据）可以有多个存储的数据物理上连续逻辑上连续插入数据速度慢（数据存储的排序）快

使用非聚集查询的时候，可以的话就避免二次查询（回表），可大大提升性能

推荐链接