数据库系列 | MySQL索引数据结构算法
1索引数据结构
索引是帮助MySQL高效获取数据的排好序的数据结构(容易忽略的点:排好序)
上图中有一张表,表名为 t ,表中有7条数据;使用 select * from t where t.clo2 = 89
查询;
若表中没有创建索引,则会全表扫描,一条一条的遍历查询,需要遍历 6 次,查询一行数据至少和磁盘做一次I/O操作(I/O是很耗性能的),至少要做 6 次 I/O 操作;
2索引数据结构
- 二叉树
- 红黑树
- Hash表
- B-Tree
1. 二叉树
语法:左边的子元素小于父元素,右边的子元素大于父元素。
字段 Col1 按照自增
如果数据是单边增长的情况 那么出现的就是和链表一样的数据结构了,树高度大。
这样查询 4 次就找到数据了;
当然,在极端情况下,若按照大小顺序插入二叉树,则会形成单边增长的二叉树,这样使用索引的时候和全表扫描是一样的了;
2. 红黑树
语法:当单边的节点大于3时候,就会自动调整,这样可以解决二叉树的弊端;红黑树也叫平衡二叉树;
同样我们查找6,在二叉树中我们需要经过6个节点才能找到(1-2-3-4-5-6),红黑树中我们只需要3个节点(2-4-6),但是mysql索引的数据结构并不是红黑树,因为如果数据量大了之后,树的高度就会很大。
当然,红黑树也有弊端的,当数据量特别大的时候,红黑树的高度特别大;假如有500W条数据,则红黑树高度为 23,若我们要查找的刚好是红黑树的叶子节点,则需要查找 23 次才可以,即要发生 23 次的磁盘 I/O 操作,性能就太差了;
3. Hash表
若索引使用的Hash存储的,存储的时候先做一次hash运算,根据 hash 的值就可以快速的定位数据的磁盘指针,这样就不管表里面有多少数据,我们的查询效率都非常的快;
在实际中为什么使用 B-Tree 或 B+Tree 来存储索引的方式更多,而不太使用 hash 呢?
- 原因1:若使用 select * from t where clo2 > 6,这种查找范围的SQL,那Hash就不能搞定了,就不会走索引了;而且对排序hash也没有办法;
- 原因2:hash会产生 hash 碰撞,MySQL的底层对hash做了处理,很少会发生hash碰撞的;
4. B-Tree
语法:叶子节点具有相同的深度,叶节点的指针为空;所有索引元素不重复;一个节点可以存储多个元素,节点中的数据索引从左到右递增排列
若 Max. Degree = 4,则如下图所示:
这样只查询 2 次就找到了;当然 B-Tree 也是有弊端的;以下是 B-Tree 的存储,数字为key,data为对应的数据;若一个节点我们申请的空间为16KB,若data中的数据过大,则一个节点能放的数据量越小,这样就会造成树的高度比较大了(比红黑树高度小点);
相关文章
- MySQL数据库原理学习(二十三)
- mysql 如何判断 “字符串” 是否为 “数字”详解数据库
- 使用Excel快速导入MySQL数据库(excle导入mysql)
- MySQL数据库与PHP乱码问题解决方法(mssqlphp乱码)
- 使用免安装MySQL:一步步简洁指引(免安装的mysql怎么用)
- MySQL定时自动导入数据,快速满足数据需求(mysql定时导入数据)
- Ubuntu安装MySQL数据库的指南(ubuntu装mysql)
- Mysql数据库研究:持续发展和应用(mysql论文)
- MySQL中文版:开放源数据库解决方案(mysql中文版)
- MySQL异常连接:排查与解决(mysql异常连接)
- 解决MySQL修改密码出错问题(mysql修改密码错误)
- 三从MySQL 双主三从主从复制实践(mysql两主)
- Mysql预处理:改变数据库访问方式(mysql的预处理)
- 排查MySQL数据库宕机排查:解决方案指南(mysql数据库宕机)
- 探索MySQL安装路径:一个指南(查看mysql安装路径)
- MySQL:强大的数据库功能之旅(mysql有哪些功能)
- 如何高效修改MySQL数据库中多个字段的方法(mysql修改多个字段)
- “——MySQL数据库连接头文件的必备指南”(mysql.h)
- MySQL内连接语句:从一张表中读取数据(mysql内连接语句)
- MySQL中文首字母排序:简易指南(mysql中文首字母排序)
- MySQL按周统计的精彩之处(mysql按周统计)
- MySQL地区数据管理与深入分析(mysql地区)
- MySQL新建连接:快速上手指南(mysql新建连接数据库)
- CentOS下搭建MySQL数据库服务器(cento mysql)
- MySQL实现一主多双主多从架构,提高数据库的可用性和性能(mysql一主多双主多从)