最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

MySQL Index 之 B+Tree数据结构

XAMPP相关 中文小张 61浏览 0评论

ySQL中90%的慢Sql都可以通过索引来得到优化,为什么索引可以使Sql变的更快,我们需要先了解下MySQL InnoDB都有哪些索引。

按规则分类:

Hash索引 Memory引擎默认 USING HASH
BTREE索引 InnoDB引擎默认B+Tree USING BTREE

按类型分类:

主键 也叫聚集索引,不允许有Null值
唯一索引 同主键,但允许有Null值
二级索引 辅助索引
全文索引 MySQL5.6以后才支持,且只能是char、varchar,text字符类型才可以创建全文索引
复合索引 多列联合的索引,可以是主键,也可以是辅助索引

数据结构:

不管哪种索引,都是一种数据结构。

哈希表 字段值通过Hash算法得出的Hash码,Hash索引中存储的即Hash码
二叉树 每个节点包含左右指针、键值、存储地址,左子树的键值小于根的键值,右子树的键值大于根的键值
平衡二叉树 每个节点包含左右指针、键值、存储地址,左子树的键值小于根的键值,右子树的键值大于根的键值,两个子树的高度最大差为1
BTree 非叶子节点也存储数据,无双向链指针
B+Tree 只有叶子节点存储数据,有双向链指针

哈希表:

哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,同时在哈希表中保存指向每个数据行的指针。检索时不需要类似B+Tree那样从根节点到叶子节点逐级查找,只需一次哈希算法即可定位到相应的位置,速度非常快。但优势只适用于键值唯一的等值查询。

二叉树与平衡二叉树:

二叉树:可以任意地构造,高度越大效率越低,以下6个值平均查找次数为(1+2+3+4+5+5)/ 6 = 3.3 次IO。

平衡二叉树:平衡二叉树简称平衡树,是由Adelson-Velskii和Landis于1962年首先提出的,所以又称为AVL树。在符合二叉树的条件下,还满足任何节点的两个子树的高度最大差为1,以下6个值平均查找次数(1+2+2+3+3+3)/ 6 = 2.3 次IO。

缺点:

大量删除、新增会导致频繁旋转;

实际运用较少,主要用于数据结构研究。

BTree:

BTree是为磁盘存储而专门设计的一类平衡搜索树,文件系统和数据库系统一般都采用BTree的数据结构,主要为提升排序和检索的效率。

由于BTree的所有节点都存储数据,这就限制了BTree节点拥有孩子节点个数,如果数据量特别大,会导致树的高度变高,IO就会增多

转载请注明:XAMPP中文组官网 » MySQL Index 之 B+Tree数据结构