石家庄做商城网站的公司,wordpress模板分享,页面设计层级一般控制()层,wordpress离线发布文章目录 1. 概述2. 常见索引结构2.1 聚簇索引2.2 二级索引(辅助索引、非聚簇索引)2.3 联合索引 3. InnoDB的B树索引的注意事项3.1 根页面位置万年不动3.2 内节点中目录项记录的唯一性 4. MyISAM中的索引方案5. InnoDB和MyISAM对比6. 小结7. 补充#xff1a;MySQL数据结构的合… 文章目录 1. 概述2. 常见索引结构2.1 聚簇索引2.2 二级索引(辅助索引、非聚簇索引)2.3 联合索引 3. InnoDB的B树索引的注意事项3.1 根页面位置万年不动3.2 内节点中目录项记录的唯一性 4. MyISAM中的索引方案5. InnoDB和MyISAM对比6. 小结7. 补充MySQL数据结构的合理性7.1 全表遍历7.2 Hash结构7.3 二叉搜索树7.4 AVL树7.5 B-Tree7.6 BTree7.7 R树 8. 思考题8.1 思考B树的存储能力如何为何说一般查找记录最多只需1~3次磁盘IO8.2 为什么说B树比B-树更适合实际应用中操作系统的文件索引和数据库索引? 9. 小结 1. 概述
索引是帮助MySQL高效获取数据的数据结构相当于书籍的目录。如果表很大有上千万条数据就意味着要做 很多次磁盘I/O才能找到需要的数据。建立索引后若根据索引innodb存储引擎使用的是B树结构查询相比按顺序查找将极大 减少磁盘I/0的次数加快查找速度降低 数据库的IO成本这也是创建索引最主要的原因
索引是在存储引擎中实现的因此每种存储引擎的索引不一定完全相同并且每种存储引擎不一定支持所有索引类型。同时存储引擎可以定义每个表的 最大索引数和 最大索引长度。所有存储引擎支持每个表至少16个索引总索引长度至少为256字节。
缺点
创建索引和维护索引要 耗费时间并且随着数据量的增加所耗费的时间也会增加索引需要占 磁盘空间索引会 降低更新表的速度 。当对表中的数据进行增删改操作的时候索引也要动态地维护这降低了数据的维护速度
因此选择使用索引时需要综合考虑索引的优点和缺点。 索引可以提高查询的速度但是会影响插入记录的速度。面临频繁增删改情况下最好的办法是先删除表中的索引然后插入数据插入完成后再创建索引。 2. 常见索引结构
首先需要知道MySQL数据库从磁盘取数据到内存中是以最小单位数据页来取的在前面章节架构篇的缓冲池中有提到默认数据页大小是16KB。
2.1 聚簇索引 特点 使用记录主键值的大小进行记录和页的排序这包括三个方面的含义 页内 的记录是按照主键的大小顺序排成一个 单向链表各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表存放 目录项记录的页 分为不同的层次在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 B树的 叶子节点 存储的是完整的用户记录 所谓完整的用户记录就是指这个记录中存储了所有列的值 (包括隐藏列)。
我们把具有这两种特性的B树称为 聚簇索引所有完整的用户记录都存放在这个 聚簇索引 的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX 语句去创建InnoDB 存储引擎会 自动 的为我们创建聚族索引索引即数据。
缺点
插入速度严重依赖于插入顺序按照主键的顺序插入是最快的方式否则将会出现页分裂严重影响性能。因此对于InnoDB表一般会定义一个自增的ID列为主键更新主键的代价很高因为将会导致被更新的行移动。因此对于innoDB表我们一般定义主键为不可更新二级索引访问需要两次索引查找 第一次找到主键值第二次根据主键值找到行数据
限制
MySQL数据库目前只有InnoDB数据引擎支持聚簇索引而MylSAM并不支持聚簇索引由于数据物理存储排序方式只能有一种所以每个MySQL的 表只能有一个聚簇索引。一般情况下就是该表的主键如果没有定义主键lnnodb会选择 非空的唯一索引 代替。如果没有这样的索引lnnodb会隐式的定义一个主键来作为聚簇索引为了充分利用聚簇索引的聚簇的特性所以innodb表的主键列尽量 选用有序的顺序id而不建议用无序的id比如UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长
2.2 二级索引(辅助索引、非聚簇索引)
上边介绍的 聚簇索引 只能在搜索条件是 主键值 时才能发挥作用因为B树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该怎么办呢?肯定不能是从头到尾沿着链表依次遍历记录一遍。 答案:我们可以 多建几棵B树不同的B树中的数据采用不同的排序规则。比方说我们用 c2 列的大小作为数据页、页中记录的排序规则再建一棵B树效果如下图所示 这个B树与上面聚簇索引有一个主要的不同点
B树的叶子节点存储的并不是完整的用户记录而是 c2列主键这两个列的值
二级索引查找流程
当根据二级索引查找时先根据二级索引找到主键值再用主键值去聚簇索引中通过主键值查找数据这个过程便是回表如果索引中便包含了所要查找的数据列如c2则不需要进行回表可直接取出数据此时便称该索引为覆盖索引
c2值相同时还会有别的处理具体可等后面看3.2。
2.3 联合索引
我们也可以同时以多个列的大小作为排序规则也就是同时为多个列建立索引比方说我们想让B树按照 c2和c3列 的大小进行排序这个包含两层含义
先把各个记录和页按照c2列进行排序在记录的c2列相同的情况下采用c3列进行排序
为c2和c3列建立的索引的示意图如下 如图所示我们需要注意以下几点
每条 目录项记录 都由 c2、c3、页号 这三个部分组成各条记录先按照c2列的值进行排序如果记录的c2列相同则按照c3列的值进行排序B树 叶子节点 处的用户记录由 c2、c3和主键c1列 组成
以c2和c3列的大小为排序规则建立的B树称为 联合索引本质上也是一个二级索引。
3. InnoDB的B树索引的注意事项
3.1 根页面位置万年不动
B树的形成过程
每当为某个表创建一个B树索引(聚族索引不是人为创建的默认就有)的时候都会为这个索引创建一个 根节点 页面。最开始表中没有数据的时候每个B树索引对应的 根节点 中既没有用户记录也没有目录项记录随后向表中插入用户记录时先把用户记录存储到这个 根节点 中当根节点中的可用 空间用完时 继续插入记录此时会将根节点中的所有记录复制到一个新分配的页比如 页a 中然后对这个新页进行 页分裂 的操作得到另一个新页比如 页b 。这时新插入的记录根据键值(也就是聚簇索引中的主键值二级索引中对应的索引列的值)的大小就会被分配到 页a 或者 页b 中而 根节点 便升级为存储目录项记录的页
这个过程特别注意的是一个B树索引的根节点自诞生之日起便不会再移动。这样只要我们对某个表建立一个索引那么它的根节点的页号便会被记录到某个地方然后凡是 InnoDB 存储引擎需要用到这个索引的时候都会从那个固定的地方取出根节点的页号从而来访问这个索引
3.2 内节点中目录项记录的唯一性
在上述二级索引中如果第二层目录项存在相同值此时需要再插入一个相同值时将无法得知将要插入的值应该插入到哪个叶子节点页面中去故实际上二级索引为保持内节点的唯一性还会再目录项中也加上主键值这样就可以在目录项c2相同的情况下再比较主键值即可得到叶子节点应该插入到哪了如下图所示 这种情况下我们需要插入(9, 1, ‘x’)时就知道我们需要插入到页5中。
4. MyISAM中的索引方案
索引/存储引擎MyISAMInnoDBMemoryB树索引支持支持支持
即使多个存储引擎支持同一种类型的索引但是他们的实现原理也是不同的。Innodb和MyISAM默认的索引是B树索引;而Memory默认的索引是Hash索引。
MyISAM引擎使用 BTree 作为索引结构叶子节点的data域存放的是 数据记录的地址。
MyISAM 的索引方案虽然也使用树形结构但是却 将索引和数据分开存储
将表中的记录 按照记录的插入顺序 单独存储在一个文件中称之为 数据文件。这个文件并不划分为若干个数据页有多少记录就往这个文件中塞多少记录就成了。由于在插入数据的时候并 没有刻意按照主键大小排序所以我们并不能在这些数据上使用二分法进行查找使用MyISAM存储引擎的表会把索引信息另外存储到一个称为 索引文件 的另一个文件中。MyISAM 会单独为表的主键创建一个索引只不过在索引的叶子节点中存储的不是完整的用户记录而是 主键值 数据记录地址 的组合 这里设表一共有三列假设我们以Col1为主键上图是一个MyISAM表的主索引 (Primary key) 示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中主键索引和二级索引(Secondary key) 在结构上没有任何区别只是主键索引要求key是唯一的而非主键索引的key可以重复故MyISAM的主键及非主键索引均为二级索引。
因此MylSAM中索引检索的算法为: 首先按照BTree搜索算法搜索索引如果指定的Key存在则取出其data域的值然后以data域的值为地址读取相应数据记录。
5. InnoDB和MyISAM对比
MyISAM的索引方式都是“非聚簇”的与InnoDB包含1个聚簇索引是不同的两种引擎中索引的区别
在InnoDB存储引擎中我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录而在 MyISAM 中却需要进行一次 回表 操作意味着MyISAM中建立的索引相当于全部都是 二级索引lnnoDB的数据文件本身就是索引文件而MyISAM索引文件和数据文件是 分离的索引文件仅保存数据记录的地址lnnoDB的非聚簇索引data域存储相应记录 主键的值而MylSAM索引记录的是地址。换句话说InnoDB的所有非聚簇索引都引用主键作为data域MyISAM的回表操作是十分 快速 的因为是拿着地址偏移量直接到文件中取数据的反观InnoDB是通过获取主键之后再去聚簇索引里找记录虽然说也不慢但还是比不上直接用地址去访问lnnoDB要求表 必须有主键( MyISAM可以没有)。如果没有显式指定则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列则MySQL自动为InnoDB表生成一个隐含字段作为主键这个字段长度为6个字节类型为长整型
6. 小结
不建议使用过长的字段作为主键因为所有二级索引都引用主键索引过长的主键索引会令二级索引变得过大用非单调的字段作为主键在innoDB中不是个好主意因为InnoDB数据文件本身是一棵BTree非单调的主键会造成在插入新记录时数据文件为了维持BTree的特性而频繁的分裂调整十分低效而使用 自增字段作为主键则是一个很好的选择分布式系统要考虑主键唯一性有雪花算法等解决方案后续研究联合索引应将数据重复少的放前面使得通过索引能按索引左侧字段尽快找到对应数据联合索引遵守最左匹配原则即查找逻辑为先查找索引最左侧字段并逐个比对而无法从索引右边字段开始
7. 补充MySQL数据结构的合理性
从MySQL的角度讲不得不考虑一个现实问题就是磁盘IO。如果我们能让索引的数据结构尽量减少硬盘的 I/0 操作所消耗的时间也就越小。可以说磁盘的 I/0 操作次数 对索引的使用效率至关重要
查找都是索引操作一般来说索引非常大尤其是关系型数据库当数据量比较大的时候索引的大小有可能几个G甚至更多为了减少索引在内存的占用数据库索引是存储在外部磁盘上的。当我们利用索引查询的时候不可能把整个索引全部加载到内存只能 逐一加载那么MySQL衡量查询效率的标准就是磁盘IO次数
7.1 全表遍历
需逐个加载数据页如果在最后一页需遍历全表将数据页都加载进内存要进行大量I/O操作。
7.2 Hash结构
哈希的查询/插入/修改/删除的平均时间复杂度都是O(1)但索引结构还是采取了树型具体原因有
Hash 索引仅能满足() ()和 IN 查询。如果进行 范围查询哈希型的索引时间复杂度会退化为O(n);而树型的“有序”特性依然能够保持O(log2N)的高效率Hash 索引还有一个缺陷数据的存储是 没有顺序的在ORDER BY的情况下使用 Hash 索引还需要对数据重新排序。对于联合索引的情况Hash 值是将联合索引键合并后一起来计算的无法对单独的一个键或者几个索引键进行查询对于等值查询来说通常 Hash 索引的效率更高不过也存在一种情况就是 索引列的重复值如果很多效率就会降低。这是因为遇到 Hash 冲突时需要遍历桶中的行指针来进行比较找到查询的关键字非常耗时。所以Hash 索引通常不会用到重复值多的列上比如列为性别、年龄的情况等
另外InnoDB 本身不支持 Hash 索引但是提供 自适应 Hash 索引 (Adaptive Hash index) 。什么情况下才会使用自适应 Hash 索引呢?如果某个数据经常被访问当满足一定条件的时候就会将这个数据页的地址存放到Hash 表中。这样下次查询的时候就可以直接找到这个页面的所在位置。这样让 B 树也具备了 Hash 索引的优点。 自适应 Hash索引变量默认是开启的
show variables like %adaptive_hash_index;7.3 二叉搜索树
如果利用树形结构作为索引结构那么磁盘的0次数和索引树的高度是相关的。如果插入数据一直是逐渐变大二叉搜索树就会形成一根链条查找数据的时间复杂度会退化为O(n)为了提高查询效率就需要尽量降低树的高度需要把原来“瘦高”的树结构变的矮胖树的每层的分叉越多越好
7.4 AVL树
为解决二叉树退化为链表的问题人们提出了平衡二叉搜索树(Balanced Binary Tree)又称AVL树有别于AVL算法。这样搜索的时间复杂度就能稳定在Log2N但是当数据量大时树的深度一样会很高而每访问一次节点就许可进行一次磁盘I/O操作需要消耗的时间一样很多。
7.5 B-Tree
针对以上问题如果把二叉树改为M叉树(M2)M叉平衡树的高度会远小于二叉树的高度所以可以让树更加“矮胖”。B树的英文是Balance Tree也就是多路平衡树。简写为B-Tree-表示两个单词相连念横杠而非B减树与B树典型区别是非叶子节点也会存储数据。对于大量的索引数据来说采用B树的结构是非常合适的因为树的高度要远小于二叉树的高度。 7.6 BTree
B树也是一种多路搜索树基于 B 树做出了改进主流的 DBMS 都支持 B 树的索引方式比如 MySQL。相比于B-TreeBTree适合文件索引系统。 BTree和B-Tree的根本差异就是B树的中间节点并不直接存储数据这样的好处是
B树的查询效率更稳定因为中间节点无需存储数据要查到数据必须查到数据的叶子节点B树的查询效率更高因为中间节点无需存储数据B树通常比B树 更矮胖查询锁需要的磁盘I/O也会更少同样的磁盘页B树可存储更多的节点关键字B树查询范围的效率更高B树叶子节点间有指针数据又是递增范围查找可通过指针连接查找而B树中要通过中序遍历效率要低很多 B树和B树都可以作为索引的数据结构在MySQL中采用的是B树但B树和B树各有自己的应用场景不能完全说B树比B树好 注意索引树不会一次性加载数据量大必然导致索引增大而是逐一加载每一个磁盘页因为磁盘页对应着索引树的节点
7.7 R树
R-Tree在MySQL很少使用仅支持 geometry数据类型支持该类型的存储引擎只有myisam、bdb、innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子: 查找20英里以内所有的餐厅。如果没有R树你会怎么解决?一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中一个字段记录经度另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息然后计算是否满足要求。如果一个地区有100家餐厅的话我们就要进行100次位置计算操作了如果应用到谷歌、百度地图这种超大数据库中这种方法便必定不可行了。R树就很好的 解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间采用了B树分割空间的思想并在添加、删除操作时采用合并、分解结点的方法保证树的平衡性。因此R树就是一棵用来存储高维数据的平衡树。相对于B-TreeR-Tree的优势在于范围查找
8. 思考题
8.1 思考B树的存储能力如何为何说一般查找记录最多只需1~3次磁盘IO
InnoDB 存储引擎中页的大小为 16KB一般表的主键类型为INT(占用4个字节或BIGINT(占用8个字节)指针类型也一般为4或8个字节也就是说一个页(BTree 中的一个节点)中大概存储16KB/(8B8B)1K个键值 (因为是估值为方便计算这里的K 取值为10^3。也就是说一个深度为3的BTree 索引可以维护10^3 * 10^ 3 * 10^3 10 亿条记录。(这里假定一个数据页也存储10^3条行记录数据了)
实际情况中每个节点可能不能填充满因此在数据库中BTree 的高度一般都在 2~4 层。MySQL的InnoDB 存储引擎在设计时是将根节点常驻内存的也就是说查找某一键值的行记录时最多只需要 1~3次磁盘I/0 操作。
8.2 为什么说B树比B-树更适合实际应用中操作系统的文件索引和数据库索引?
B树的磁盘读写代价更低B树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了B树的查询效率更加稳定
9. 小结
使用索引可以帮助我们从海量的数据中快速定位想要查找的数据不过索引也存在一些不足比如占用存储空间、降低数据库写操作的性能等如果有多个索引还会增加索引选择的时间。当我们使用索引时需要平衡索引的利(提升查询效率)和弊(维护索引所需的代价)。
在实际工作中我们还需要基于需求和数据本身的分布情况来确定是否使用索引尽管 索引不是万能的但 数据量大的时候不使用索引是不可想象的 毕竟索引的本质是帮助我们提升数据检索的效率
