索引的数据结构

概述

我们知道索引是帮助MySQL高效获取排好序数据结构

为什么使用索引后查询效率提高很多呢?接下来我们来了解下。

CbsG9Y.png

​ 在没有索引的情况下我们执行一条sql语句,那么是表进行全局遍历,磁盘寻址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。

select  * from user where col1=6;


​ 为了加快的查找效率,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找快速获取到相应数据。

select  * from user where col2=59;

常见的数据结构

1.二叉树:对于当前父节点,左分支节点元素小,右分支节点元素大

二叉树示意图

2. 红黑树:红黑树是一种平衡二叉树,目的是寻求左右分支长度的平衡
红黑树(平衡二叉树)
3. BTree:多叉平衡查找树,每个节点都可以存放多个数据,可以有效减少层数(高度)
多叉平衡查找树
4. B+Tree:针对于BTree的优化,数据只存储在叶子节点上,非叶子节点只存储索引和指针
B+Tree
5. Hash
哈希散列

MySQL没有推荐使用hash作为索引原因是因为hash是无序

数据结构学习网站

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

MySQL中的B+Tree

-- 查看mysql索引节点大小
show global status like 'innodb_page_size';

MySQL中的 B+Tree 索引结构示意图:

Cbs3A6.png

数据库的存储引擎

MySQL存储引擎的不同,那么索引文件保存的方式也有所不同,常见的有二种存储引擎MyISAMInnoDB

MyISAM

MySQL5.5之前默认使用的存储引擎,不支持事务和外键约束

CREATE TABLE `tb_myisam` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `username` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CbsJr5.png

Cbss10.png

为什么myisam查询速度比innodb快?

Cbstlm.png

InnoDB

MySQL5.5之后默认使用的存储引擎,支持事务,支持外键约束

CREATE TABLE `tb_innodb` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `username` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Cbs4Ih.png

CbsiNr.png

innodb的非主键索引也称为:非聚集索引

CbsnuT.png

面试题

为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?

  • 第一问考察的内容是innodb的存储引擎的索引特点:聚集索引
  • 第二问考察的内容是B+Tree的数据结构(字符串比较慢、字符串是无序在新增时会加大叔裂变)
最后修改:2021 年 09 月 08 日 11 : 13 AM
如果觉得我的文章对你有用,请随意赞赏