东营建设网站,网站的界面设计怎么做,优秀企业,关于网站建设实验报告索引数据结构-B-Tree索引、Hash索引、空间索引、全文索引
二叉树查找
对于相同深度的节点#xff0c;左侧的节点总是比右侧的节点小。在搜索时#xff0c;如果要搜索的值key大于根节点#xff08;图中6#xff09;#xff0c;就会在右侧子树里查找#xff1b;key小于根…索引数据结构-B-Tree索引、Hash索引、空间索引、全文索引
二叉树查找
对于相同深度的节点左侧的节点总是比右侧的节点小。在搜索时如果要搜索的值key大于根节点图中6就会在右侧子树里查找key小于根节点图中6就会在左侧子树里查找
比如查找图中2先找到根节点6然后使用2与6对比小于6在左侧查找。然后再将2与3对比小于3在左侧查找然后将2与2对比相等故找到节点2。
只需要三次找到就能找到节点2。
并且对于图中这样一棵树由于它的深度是3不管哪个元素最多只需要3次查找就能找到对应的节点。 但是假设是下面图中的二叉树如果想要搜索的值key是8则需要5次查找。
并且对于图中这样一棵树由于它的深度是5则最多需要5次查找就能找到对应的节点。 从上可以知道两个二叉树都是6个节点但是查询效率是不一样的。后面的二叉树比前面的性能要差一些。
因为下面的二叉树不够平衡导致的所谓的不够平衡就是一棵二叉树左侧的节点和右侧的节点严重不一致。
于是就有了平衡二叉树的概念。也叫AVL树。
在普通二叉搜索树上增加了一个约束每个节点的左子树和右子树的高度差不超过1。
平衡二叉搜索树AVL树
每个节点的左子树和右子树的高度差不超过1 可以看到上面前面的二叉树就是一个平衡二叉搜索树它的左子树和右子树的高度差都是小于等于1。但是上面后面的二叉树就不是一个平衡二叉搜索树比如2节点的左子树高度是0右子树高度是4超过1了。 对于n个节点树的深度是log2n查询的时间复杂度是O(log2n) 对于一个有64个节点的平衡二叉树最多只需要查找6次就能找到任意一个节点但是假设n非常大比如10000那么这个树的深度依然比较高这意味着查询的次数也会很多于是就出现如果不是一个二叉树而是一个m叉树。比如5叉树一个节点存在五个子节点这样树的深度就可以变小一些。当我们像定位某个节点的时候查询的次数就减少了就产生了B-Tree树
B-Tree树Balance Tree 读作B Tree不是B减Tree不是减是杠 B-Tree全称Balance Tree意思是平衡多路搜索树 下面图展示3阶的B-Tree阶是构建B-Tree的一个参数可以认为是一个数字阶越大表示一个节点的子节点越多。 图中指针指向子节点对应的磁盘块。 关键字可以想象成表的主键或者索引。 数据指的是关键字所对应的数据可以理解为表里面某一行的数据。 比如图中17 Data就可以理解为主键等于17的那一条数据也可以理解为有一个索引这个索引字段的值为17Data是17对应的数据 假设要搜索主键等于5的数据首先找到根节点里面的关键字17和35进行比较后发现5小于17就可以通过P1指针定位到磁盘块2而磁盘块2里面的关键字是8和12进行比较后发现5小于8于是通过磁盘块2P1指针找到磁盘块5最后在磁盘块5里面就可以找到这条数据了。 ps图中磁盘块3也有3个子节点只是图中没有画。
B-Tree树特性 根节点的子节点个数2xmm是树的阶 假设m3则根节点可以有2-3个孩子 中间节点的子节点个数m/2ym 假设m3中间节点至少有2个孩子最多3个孩子 每个中间节点包含n个关键字n子节点个数-1且按升序排序 如果中间节点有3个子节点则里面会有2个关键字且按升序排序 Pi(i1,…n1)为指向子树根节点的指针其中P[1]指向关键字小于Key[1]的子树P[i]指向关键字属于Key[i-1],Key[i]的子树P[n1]指向关键字大于Key[n]的子树 每个节点包含n个关键字则就会有n1个指针 P1、P2、P3为指向子树根节点的指针P1指向关键字小于Key1的树P2指向Key1-Key2之间的子树P3指向大于Key2的树
B-Tree树总结
通过B-Tree树可以有效的把树的高度降下来。树的阶越大树的高度越低查询的次数也会越少。
BTree树 读作B加Tree BTree树是B-Tree树基础上的一种优化 MySQL里面的InnoDB存储引擎就是使用BTree树实现其索引结构 假设查找图中主键等于8的数据先通过根节点将8和5、28进行对比发现8大于5小于28于是使用P1指针找到磁盘块2。接着再用8与5、10对比发现8大于5小于10。于是使用磁盘块2里面的P1指针找到数据8 B-Tree和BTree的差异 BTree有n个子节点的节点中含有n个关键字 B-Tree是n个子节点的节点有n-1个关键字上图B-Tree里面3个子节点只包含了2个关键字而BTree里面3个子节点只包含了3个关键字 BTree中所有叶子节点中包含了全部关键字的信息且叶子节点按照关键字的大小自小而大的顺序链接构成一个有序链表最显著的差异 B-Tree的叶子节点不包括全部关键字比如图中BTree根节点里面的5、28、65会在中间节点里面展示出来中间节点里面的5、10、20又会在叶子节点里面展示出来。且叶子节点里面包含所有关键字的信息不管哪一个父节点里面的关键字在叶子节点里面都会记录一份 BTree中非叶子节点仅用于索引不保存数据记录记录存放在叶子节点中 B-Tree中非叶子节点既保存索引也保存数据记录
B-Tree VS BTree
where id 5这种情况都是查询了3次查询过程区别不大但是由于BTree的中间节点只用来索引所以对于相同的空间BTree里面存储的关键字更多于是BTree相对就更加矮胖一些所以磁盘IO的次数就少一些。由于B-Tree的中间节点也存储数据所以它的查询效率不是很稳定最好的情况是在根节点就直接查询到数据了而最差的情况是下叶子节点才能找到数据。而BTree不管什么时候都必须要到叶子节点才能获得数据这是因为BTree里面非叶子节点不存储数据只是用来索引。where id between 5 and 10B-Tree需要先查5再查6…最后查10最后再把结果组成到一起返回。BTree只需要先查5然后通过5这个叶子节点的有序链表依次遍历一直遍历到10即可不需要像B-Tree一样挨个查再组装数据所以BTree对于范围查询的性能要比B-Tree好
InnoDB存储方式
使用BTree索引主键索引叶子节点存储主键以及主键对应的数据内容非主键索引二级索引、辅助索引叶子节点存储索引以及数据对应的主键故如果sql查询是根据非主键索引查询先是通过主键索引查询主键再通过主键查询数据
MyISAM存储方式
使用BTree索引主键索引/非主键索引的叶子节点都是存储指向数据块的指针也就是说MyISAM存储方式里面索引和数据是分开存储的
InnoDB VS MyISAM
InnoDB聚簇索引MyISAM非聚簇索引
Hash索引 图中buckets是索引字段计算出来的hash值和对应数据的物理位置组成的哈希表都知道哈希表是数组链表的组合数组存储就是索引字段计算出来的hash值链表存储的就是对应数据的物理位置。而entries是具体的数据。
这样Hash索引的核心就是哈希表每条数据都会基于索引字段计算出hashcode存放在buckets中查询时根据索引字段计算出hashcode从buckets中查询。故正常情况的时间复杂度时O(1)。性能很好。
假设出现了哈希冲突比如图中阿神和姚半仙的hashcode都是139。当查询条件是姚半仙会先用姚半仙计算出hashcode得出139然后到buckets中匹配找到hashcode是139的指针数组或者是链表这个需要看数据引擎是如何实现的之后再通过指针数组或者是链表找到对应的数据。
可以发现在哈希冲突的情况下性能会降低一些所以说使用Hash索引要尽量防止哈希冲突。
Hash索引支持情况
Memory引擎支持显式定义Hash索引InnoDB引擎支持“自适应Hash索引” 当InnoDB发现某些索引值使用非常频繁的话那么它会在内存里面基于BTree索引之上再创建一个Hash索引提升查询效率“自适应Hash索引”我们没法直接介入MySQL官方只提供了一个开关可以使用SHOW VARIABLES LIKE ‘innodb_adaptive_hash_index’;指令查看开关状态默认是开启的ON状态可以使用SET GLOBAL innodb_adaptive_hash_index ‘OFF’;指令设置开发状态正常情况保持默认ON状态即可 测试 CREATE TABLE t_test_hash ( NAME VARCHAR ( 45 ) NOT NULL, age TINYINT ( 4 ) NOT NULL, KEY USING HASH ( NAME ) ) ENGINE memory;可以创建成功CREATE TABLE t_test_hash ( NAME VARCHAR ( 45 ) NOT NULL, age TINYINT ( 4 ) NOT NULL, KEY USING HASH ( NAME ) ) ENGINE INNODB;会发现也可以创建成功但是可以使用SHOW INDEX FROM t_test_hash;语句查看真正的索引是btree索引
空间索引R-Tree索引
存储GIS数据基于R-Tree在早期只有MyISAM引擎支持空间索引但是MySQL 5.7时开始InnoDB支持空间索引目前MySQL对于GIS的支持并不是很完善所以大部分人都不会用到相关的功能在GIS领域里面做得比较好的是空间数据库PostgresqlPostgis拓展R-Tree介绍文章参考https://blog.csdn.net/sjyttkl/article/details/70226192空间索引使用文章参考https://www.cnblogs.com/oloroso/p/9579720.html
全文索引【了解即可】
适应全文搜索的需求MySQL 5.7之前全文索引不支持中文经常搭配SphinxMySQL 5.7起内置ngram支持中文 ngram官方地址https://dev.mysql.com/doc/refman/8.0/en/fulltext-search-ngram.html 但是由于时代变化目前来说应对全文搜索的需求我们更多的会使用一些搜索引擎比如elasticsearch、solr等所以全文索引用的不是很多只需要了解即可全文索引使用文章参考https://blog.csdn.net/mrzhouxiaofei/article/details/79940958
B-Tree(BTree)、Hash索引的特性与限制
B-Tree(BTree)特性
完全匹配index(name) where name 大目’可以使用索引范围匹配index(age) where age 5可以使用索引前缀匹配index(name) where name like 大%可以使用索引 但是%在前面就无法使用索引了即右模糊可以使用索引左模糊不可以使用索引
B-Tree(BTree)限制——最左优先原则
创建组合索引index(name,age,sex) 查询条件不包括最左列无法使用索引 例如where age 5 and sex 1不包括name所以无法使用索引 跳过了索引中的列则无法完全使用索引 例如where name ‘大目’ and sex 1 只能用到name这一列索引而sex字段因为跳过了age字段无法使用索引 查询中有某个列的范围模糊查询则其右边所有列都无法使用索引 例如where name ‘大目’ and age 32 and sex 1 只能用到name、age这两列索引 最左优先原则指的是索引按照最左优先的方式匹配索引不满足以上三个条件时都无法完全使用索引因此当使用B-Tree(BTree)索引时索引列的顺序是非常重要的。以上的几个例子都和索引的顺序有关那么在做性能调优时我们常常需要根据查询条件看看索引需要的字段甚至需要额外创建一些使用的列相同但是列顺序不同的索引
Hash索引
一般性能比B-Tree(BTree)要好一些只要不产生哈希冲突时间复杂度就是O(1)
Hash索引限制
Hash索引并不是按照索引值排序所以无法使用排序 这意味着如果查询条件带order by是无法使用Hash索引的 Hash索引不支持部分索引列匹配查找 hash(a,b) where a 1不走索引这是因为Hash索引是使用索引列的全部内容计算的 Hash索引只支持等值查询例如 、IN不支持范围查询例如 、、between…and…、模糊查询likeHash索引的Hash冲突越严重性能下降越厉害
创建索引的原则
哪些场景建议创建索引哪些场景不建议创建索引
建议创建索引的场景 select语句频繁作为where条件的字段一般需要创建索引 -- 如果频繁使用first_name字段作为查询条件就创建索引index(first_name)
SELECT * FROM employees WHERE first_name Georgi;-- 如果频繁使用first_name和last_name字段作为查询条件可以创建索引index(first_name, last_name)
-- 如果有一个动态查询first_name是个必填条件、last_name是个可选条件创建索引index(last_name, first_name)根据最左前缀原则WHERE first_name Georgi无法使用该索引
SELECT * FROM employees WHERE first_name Georgi AND last_name Cools;update/delete语句where条件的字段一般需要创建索引。因为update/delete语句需要先根据where条件查询出数据再更新或者删除数据 -- 例如以下sql就需要为emp_no创建索引但是emp_no已经是主键索引就不需要创建了
UPDATE employees SET first_name Jim WHERE 100001;-- 例如以下sql就需要为first_name创建索引
DELETE FROM employees WHERE first_name Georgi;需要分组、排序的字段一般需要创建索引。 -- 例如以下sql就需要为GROUP BY和ORDER BY字段dept_no创建索引
SELECT dept_no, count( * ) FROM dept_emp GROUP BY dept_no;
SELECT dept_no, count( * ) FROM dept_emp ORDER BY dept_no;distinct所使用的字段一般需要创建索引。 -- 例如以下sql就需要为first_name字段创建索引
SELECT DISTINCT(first_name) FROM employees;字段的值有唯一性约束一般需要创建索引。而一些索引本身就可以起到唯一性约束的作用比如唯一索引、主键索引等 对于多表查询连接的字段应创建索引且类型务必必保持一致为了避免隐式转换隐式转换可能会导致索引无法使用 -- 查询工号为100001的雇员待过的部门
-- emp.emp_no和de.emp_no、de.dept_no和d.dept_no的字段类型就需要保持一致否则就会导致隐式转换从而可能导致索引无法使用
SELECTemp.*,d.dept_name
FROMemployees empLEFT JOIN dept_emp de ON emp.emp_no de.emp_noLEFT JOIN departments d ON de.dept_no d.dept_no
WHEREde.emp_no 100001;不建议创建索引的场景 where子句里面用不到的字段。因为索引的作用是为了快速定位到需要查询的数据 表的记录非常少。因为即使创建了索引对性能影响并不大 有大量重复数据选择性低。因为此时创建索引的作用是不大的也不建议创建索引 因为索引的选择性越高查询效率越好因为可以在查找时过滤更多行从而提升查询效率 这也是唯一索引比普通索引查询效率好的原因 而如果存在大量重复数据那么索引的效率也会越低 比如有个人员表里面的性别字段就不适合创建索引因为性别字段的值存在大量重复数据选择性很低。 频繁更新的字段如果创建索引要考虑其索引维护开销 因为在更新或者删除数据的时候也需要更新索引如果更新频繁的字段而查询很少的话是不适合创建索引的因为每次更新数据都要去维护索引信息
ps创建索引的原则只是参考不要死守教条
