网站建设实践总结,唐山网站建设费用,学网站开发和游戏开发那个,建筑工程公司名字大全集目录
索引(INDEX)基本概念
索引结构分类
BTree树索引结构
Hash索引结构
Full-Text索引
R-Tree索引 索引(INDEX)基本概念
什么是索引
索引是帮助MySQL高效获取数据的有序数据结构
为数据库表中的某些列创建索引#xff0c;就是对数据库表中某些列的值通过不同的数据结…目录
索引(INDEX)基本概念
索引结构分类
BTree树索引结构
Hash索引结构
Full-Text索引
R-Tree索引 索引(INDEX)基本概念
什么是索引
索引是帮助MySQL高效获取数据的有序数据结构
为数据库表中的某些列创建索引就是对数据库表中某些列的值通过不同的数据结构进行排序
为列建立索引之后数据库除了维护数据之外还会维护满足特定查找算法的数据结构这些数据结构以某种方式指向数据这样就可以在这些数据结构上实现快速查询这种数据结构就是索引
索引的作用
通过索引可以将无序的数据变为有序的数据能够实现快速访问数据库表中的特定信息
优缺点
优点
提高数据检索的效率降低数据库的IO成本
通过索引对数据进行排序降低数据排序的成本降低CPU的消耗
缺点
索引会占用空间
索引提高了表的查询效率但是却降低了更新表的速度Insert、Update、Delete
索引只是一个提高效率的因素如果MySQL有大数据量的表就需要花时间研究最优秀的索引即需要研究为哪些字段建立索引能够使得效率提升到最大化因为一条查询语句只会引用到一种索引并且一般建议一个表建立的索引数量不要超过5个 索引结构分类
索引结构主要分为四大类
BTree索引-B树
最常见的索引类型大部分的存储引擎都支持此索引
Hash索引-Hash表
底层的数据结构是用哈希表实现的只有精确匹配索引列的查询才有效不支持范围查询
Full-Text索引-倒排索引
又名全文索引是一种通过建立倒排索引快速匹配文档的方式
R-Tree索引R-Tree树
又名空间索引是MyISAM引擎的一个特殊索引类型主要用于地理位置数据使用较少
存储引擎对不同索引的支持情况默认BTree索引 在MySQL数据库中支持Hash索引的是Memory引擎而InnoDB中具有自适应Hash的功能根据Btree索引在指定条件下自动构建的 BTree树索引结构
BTree树是由二叉树 → 红黑树自平衡二叉树 → B-Tree树烟花而来的我们在介绍BTree树之前先介绍这三种数据结构
二叉树
二叉树的每个节点最多有两个子节点两颗子树并且两个子节点是有序的
以单个节点为例左边子节点是比自身小的右边子节点是比自身大的
缺点
大数据量的情况下层级较深检索速度慢容易形成倾斜树左倾斜或右倾斜 二叉树的工作原理 二叉树的数据插入依次插入30、40、20、19、21、39、35 二叉树的数据遍历 二叉树的数据查找查找39 、21、25 二叉树的数据删除依次删除19、39、30 红黑树自平衡二叉树
红黑树时二叉树的变种可以解决二叉树插入数值时产生斜树的问题
任何一个节点都有颜色(红色或黑色)通过颜色来确保树在插入和删除时的平衡
根节点一定是黑色的Null节点被认为是黑色的每个红色节点的两个叶子节点都是黑色
每个叶子节点到根的路径上不能出现连续的红色节点
任何一个节点到达叶子节点所经过的黑节点个数必须相等
当在红黑树中进行插入和删除操作时会通过左旋、右旋、重新着色来修复树结构保持树的平衡
缺点
在进行大量插入和删除操作的情况下可能会造成频繁的树重构影响性能红黑树的实现比较复杂需要维护节点的颜色和平衡红黑树本质也是二叉树在大数据量的情况下层级较深检索速度会下降
红黑树的工作原理
红黑树的数据插入依次插入30、40、20、19、21、39、35 使用到了右旋 红黑树的数据遍历 红黑树的数据查找查找39 、21、25 红黑树的数据删除依次删除19、39、30 B-Tree树多路平衡查找树
二叉树一个Node节点只能够存储一个Key和一个Value并且只有两个子节点而多路树相比较而言一个Node节点能够存储更多的Key和Value能够携带更多的子节点建树高度会比二叉树要低
B-Tree树的一个节点能够存储多少Key和Value可以有多少个子节点通过最大度数MAX-Degree 也称为阶数决定
一个m阶的B-Tree树 树中的每个节点最多有m个子节点m-1个Key和Value两个子树的指针夹着一个Key和Value 树的根节点至少有一个Key和Value至少两个子节点
缺点
B树的叶子节点和非叶子节点都会保存数据使得非叶子节点保存的指针量变小
如果存储大量的数据需要增加树的高度导致IO操作变多查询性能变低 B-Tree树的工作原理
B-Tree树的数据插入Max-Degree为3依次插入30、40、20、19、21、39、35 B-Tree树的数据遍历 B-Tree树的数据查找查找39 、21、25 B-Tree树的数据删除依次删除19、39、30 BTree树
BTree树是B-Tree树的变种也是一种多路搜索树定义基本与B-Tree相同
BTree只有叶子节点存储数据并且所有的元素都会出现在叶子节点中所有叶子节点形成了一个单向链表叶子节点将数据按照大小排列并且相邻叶子节点之间按照大小排列
非叶子节点不存储数据只存储Key只是起到索引的作用在相同的数据量下BTree树更加矮壮 B-Tree树的工作原理
BTree树的数据插入Max-Degree为3依次插入30、40、20、19、21、39、35 BTree树的数据遍历 BTree树的数据查找查找39 、21、25 BTree树的数据删除依次删除19、39、30 MySQL的BTree索引结构
MySQL的索引数据结构对经典的BTree进行了优化在原BTree的基础上增加了一个指向相邻叶子节点的链表指针所有叶子节点形成了一个双向链表提高了遍历速度
MySQL在查询是根据查询条件查询对应的键值Key然后将键值对应数据Value提取出来 Hash索引结构
哈希索引就是采用一定的hash算法将键值换算成新的Hash值将哈希值映射到一个桶中桶中存储了所有哈希值相同的数据行的指针然后存储在Hash表中
当查询时MySQL会先通过哈希函数计算出查询条件的哈希值在Hash表中查找对应的桶然后在对应的桶中查找相应的数据行
哈希冲突
如果两个或多个键值映射到同一个相同的槽位桶则他们就产生了hash冲突通过链表解决 特点
Hash索引只能够用于对等比较in等不支持范围查询between等无法利用Hash索引完成排序操作因为Hash索引中存放的是经过Hash计算后的Hash值此值的大小并不一定和Hash运算之前的键值完全一样Hash索引无法避免表扫描即每次都要全表扫描因为Hash索引是将键值通过Hash运算之后将其结果和对应的行指针信息存放在一个Hash表中由于不同的索引键可能存在相同的Hash值也就是哈希冲突所以满足某个Hash键值的数据的记录跳数无法直接从Hash索引中直接完成查询还是要通过访问表中的实际数据进行比较并得到相应的结果对于联合索引Hash不能使用部分索引键查询要么全部使用要么全部不使用Hash只需要做一次运算就可以找到该数据所在的桶不像树结构那样从根、叶子节点的顺序来查找所以Hash索引的查询效率理论上是要高于BTree的不过对于存在大量Hash值相同的情况下性能不一定比BTree高
Full-Text索引
通过建立倒排索引Inverted Index构建Full-Text索引提高数据的检索效率
倒排索引是一种将文档中的单词/汉字映射到其出现位置的数据结构主要用来解决判断字段的值中 是否包含 某字符/汉字的问题
我们对于简单业务或者数据量小的业务可以通过Like()关键字来判断但是对于大数据量业务使用Like效率会大大降低
不同存储索引对Full-Text索引的支持
在MySQL5.6版本之前只有MYISAM存储引擎支持全文索引
在MySQL5.6版本之后InnoDB能够支持全文索引不过只支持对英文的全文索引不支持中文的全文索引后续通过内置分词器ngram来支持中文索引
配置ngram的最小长度
在MySQL的配置文件中添加以下字段
ft_min_word_len 2 #此最小长度就是分词的最小长度默认为2
即对于一段语句可以分为多个汉字组每个汉字组最少都有2个汉字 我想学习数据库 可以分词为 我想 学习 数据库 三个组
一般不会将ngram设置的很小如果很小的话会占用大量的空间因此我们一般都不修改此最小长度就默认为2
全文索引的流程
用户输入要查找的内容 → SQL执行引擎 → ngram对查找的内容进行分词 → 把分词后的词依次的去倒排索引中去查找 → 将相应的记录返回
分词器ngram在建立索引时会对字段中的值进行分词在进行查询时也会对要查找的内容分词
R-Tree索引
构建空间索引有多种数据结构例如四叉树、R-Tree树
在MySQL中是通过R-Tree树来构建空间索引的是一种加快空间数据查询速度的技术
R-tree将空间数据分割成一系列矩形区域每个节点可以表示一个矩形区域同时可以包含其他节点或数据项。这种层级结构允许MySQL在空间查询中更快地定位所需的数据减少搜索范围从而提高查询性能
例如
一个表中的某字段存储着一个地方餐馆的经纬度位置信息现在我们需要根据我们的位置找附近1公里的餐馆
我们可以通过计算我们的位置找到附近1公里范围内的经纬度范围然后查询表中的满足此经纬度的值为了加快检索效率我们就可以对存储经纬度位置信息的字段建立空间索引
R-Tree的构建过程——R树是把B树的思想扩展到了多维空间
1、数据划分
所有的数据项也成为对象点、线或面都被视为一个单独的矩形
2、构建叶子节点叶子节点是R树的底层节点
将划分好的矩形进行分组并构建叶子节点每个叶子节点包含多个对象及其对应的矩形
3、合并叶子节点
当叶子节点的数目超过了R-Tree规定的最大容量此时R树会尝试合并相邻的叶子节点来减少树的高度和提高查询效率
4、构建非叶子节点
将合并后叶子构建为新的非叶子节点非叶子节点也是一个矩形包含了其所有子节点的矩形范围
5、递归构建
重复上述的操作知道构建出整个R树的根节点R树的最顶层节点将包含所有的数据范围
具体R树的构建方式可以参考以下文章
从B树、B树、B*树谈到R 树_v_JULY_v的博客-CSDN博客https://blog.csdn.net/v_JULY_v/article/details/6530142
