精华内容
下载资源
问答
  • MySQL索引实现原理分析

    万次阅读 多人点赞 2018-10-10 17:59:07
    MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。MyISAM索引实现MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的...

           目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。MyISAM索引实现MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:image.png这里设表一共有三列,假设我  

            在 MySQL 中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论 MyISAM 和 InnoDB 两个存储引擎的索引实现方式。

    MyISAM 索引实现 

    MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图:
    MySQL索引实现原理分析

    这里设表一共有三列,假设我们以 Col1 为主键,则图 8 是一个 MyISAM 表的主索引(Primary key)示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。

    辅助索引 

    在 MyISAM 中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求 key 是唯一的,而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引,则此索引的结构如下图所示


    MySQL索引实现原理分析

    同样也是一颗 B+Tree,data 域保存数据记录的地址。因此,MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引,如果指定的 Key 存在,则取出其data 域的值,然后以 data 域的值为地址,读取相应数据记录。

    MyISAM 的索引方式也叫做“非聚集索引”,之所以这么称呼是为了与 InnoDB的聚集索引区分。


    InnoDB 索引实现 

    虽然 InnoDB 也使用 B+Tree 作为索引结构,但具体实现方式却与 MyISAM 截然不同。

    1.第一个重大区别是 InnoDB 的数据文件本身就是索引文件。从上文知道,MyISAM 索引文件和数据文件是分离的,索引文件仅保存数据记录的地址

    而在InnoDB 中,表数据文件本身就是按 B+Tree 组织的一个索引结构,这棵树的叶点data 域保存了完整的数据记录。这个索引的 key 是数据表的主键,因此 InnoDB 表数据文件本身就是主索引。


    MySQL索引实现原理分析

    上图是 InnoDB 主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集,

     1 .InnoDB 要求表必须有主键(MyISAM 可以没有),如果没有显式指定,则 MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL 自动为 InnoDB 表生成一个隐含字段作为主键,类型为长整形。

     同时,请尽量在 InnoDB 上采用自增字段做表的主键。因为 InnoDB 数据文件本身是一棵B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:


    MySQL索引实现原理分析

    这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

     2.第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说,InnoDB 的所有辅助索引都引用主键作为 data 域。
    例如,图 11 为定义在 Col3 上的一个辅助索引:


    MySQL索引实现原理分析
     

    聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引(回表):首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

     引申:为什么不建议使用过长的字段作为主键?

     因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。


    聚簇索引与非聚簇索引 

    InnoDB 使用的是聚簇索引, 将主键组织到一棵 B+树中, 而行数据就储存在叶子节点上, 若使用"where id = 14"这样的条件查找主键, 则按照 B+树的检索算法即可查找到对应的叶节点, 之后获得行数据。 若对 Name 列进行条件搜索, 则需要两个步骤:
    第一步在辅助索引 B+树中检索 Name, 到达其叶子节点获取对应的主键。
    第二步使用主键在主索引 B+树种再执行一次 B+树检索操作, 最终到达叶子节点即可获取整行数据。

    MyISM 使用的是非聚簇索引, 非聚簇索引的两棵 B+树看上去没什么不同, 节点
    的结构完全一致只是存储的内容不同而已, 主键索引 B+树的节点存储了主键, 辅助键索引B+树存储了辅助键。 表数据存储在独立的地方, 这两颗 B+树的叶子节点都使用一个地址指向真正的表数据, 对于表数据来说, 这两个键没有任何差别。 由于索引树是独立的, 通过辅助键检索无需访问主键的索引树。

    为了更形象说明这两种索引的区别, 我们假想一个表如下图存储了 4 行数据。 其中Id 作为主索引, Name 作为辅助索引。 图示清晰的显示了聚簇索引和非聚簇索引的差异


    MySQL索引实现原理分析

     

    联合索引及最左原则

    联合索引存储数据结构图:

    最左原则:

    例如联合索引有三个索引字段(A,B,C)

    查询条件:

    (A,,)---会使用索引

    (A,B,)---会使用索引

    (A,B,C)---会使用索引

    (,B,C)---不会使用索引

    (,,C)---不会使用索引

     

    *最后来一个问题:mysql假设一行数据大小为1k,则一颗层高为3的b+树可以存放多少条数据?

    mysql页默认大小16k,如果数据行大小1k,叶子节点存放的完整数据,则叶子节点一页可以放16条数据;非叶子节点页面存放的是主键和指针,所以主要看主键是啥类型,假设是integer,则长度8字节,指针大小在innodb是6字节,一共14字节,所以非叶子节点每页可以存16384/14=1170个主键数据(1170个分叉),则三层b+树数据可以存1170*1170*16=21902400条数据。(千万级别)

    展开全文
  • MySql 创建索引过程:首先进行该字段的排序,再生成叶子节点,再生成枝节点,最后生成根节点。 整个索引的结构就生成完毕了,如下图: 举个例子:有100条数据,ID为1-100,以这个ID建立索引,我们来查找ID在50-...

    总所周知,数据库查询优化离不开索引,虽然它是个简单的东西,可是其中却大有学问。

    因追求极简,直接讲解其中原理

    先来讲解一下索引的优缺点叭,一句话就可以概括,以空间换时间。

    MySql  创建索引过程:首先进行该字段的排序,再生成叶子节点,再生成枝节点,最后生成根节点。

    整个索引的结构就生成完毕了,如下图:

     

    举个例子:有100条数据,ID为1-100,以这个ID建立索引,我们来查找ID在50-73之间的数据集合,

    如图中红色箭头所示,只需要5次IO就可以查询出需要的数据。

    索引分两种,聚簇索引和非聚簇索引,首先我们来看第一种

    聚簇(区)索引:

    1. 如果表中设置了主键(例如ID列),自动根据ID列生成索引树
    2. 如果没有设置主键,自动选择第一个唯一键的列作为聚簇索引
    3. 自动生成隐藏的聚簇索引

    接下来我们看看B-Tree的构建过程:

    • 叶子节点: 存储数据行时就是有序的,直接将数据行的page作为叶子节点(相邻的叶子结点,有双向指针)
    • 枝节点  : 提取叶子节点ID的范围+指针,构建枝节点(相邻枝节点,有双向指针)
    • 根节点  : 提取枝节点的ID的范围+指针,构建根节点

    接下来,来看看数据库实际数据存放:

    B-Tree算法演变

     

     

    展开全文
  • Mysql索引实现原理与创建索引

    千次阅读 多人点赞 2019-02-25 17:56:42
    索引用于快速找出在某个列中有 一特定的值的行,不使用索引Mysql 必须从第一条记录开始读完整个表,表越大,查询数据所花费的的时间越多。如果表中查询的列有一个索引Mysql 能够快速到达一个位置去搜索...

    索引:

    提高查询效率,
    消除数据分组/排序,
    避免 “回表” 查询 ,
    优化聚合查询,
    用与多表 JOIN 关联查询,
    利用唯一性约束保证数据唯一性,
    lnnoDB行锁实现。

    什么是索引:

    索引用于快速找出在某个列中有 一特定的值的行,不使用索引,Mysql
    必须从第一条记录开始读完整个表,表越大,查询数据所花费的的时间越多。如果表中查询的列有一个索引,Mysql 能够快速到达一个位置去搜索数据文件。而不必查看所有的数据。那么将节省很大一部分时间。
    索引的优势和劣势
    优势: 索引就像书本的目录 使查找更容易方便 提高 数据检索效率,降低数据库的成本
    @:有效的提高检索效率,最终还是为了减少对io的读取
    通过索引对数据库进行排序,降低数据排序的成本,降低 cpu 的消耗
    @:索引是排好序的数据结构,但是他也是需要运算成本的,会消耗一定的系统资源
    但是不用索引数据量多得话或消耗更多的资源,减少了多电脑cpu的消耗
    劣势: 实际上索引也是一张表,改表保存了主键 与索引字段,并指向实体表的记录,所以索列也
    是要占空间的。
    虽然索引大大提高了 查询的速度,同时却会降低更新表的速度, 如果对 表 进行 insert ,
    update delete 整个数据结构和索引都会跟着更新,

    使用索引注意:
    1:如果数据频繁更新的话就不适合使用索引
    2:那些根本就不会作为where条件后的那些字段
    4:表数据很少的时候不适合使用索引什么时候适合建索引和以上条件相反的时候就适
    合建索引
    5: 过多的索引的的索引和不适合的索引 都不是好事 会增加io的成本

    mysql 是存在磁盘里的
    mysql 的索引是缓存在磁盘里的数据
    N磁盘 取数据 ---->到内存
    磁盘 也就是
    在这里插入图片描述

    索引的分类:

    单值索引:既一个索引只包含单个列,一个表可有多个单列索引。
    (1:每个索引只包含一列
    2:每个表中可以有多个单列索引,但他们不是组合索引)
    普通索引
    特点:1,允许定义索引的列中有空值和重复值
    2:没有指定的关键字 默认使用的就是普通索引
    语法: create index 索引名称 on 表名称(字段名称)
    删除索引的语法
    drop index 索引名称 on 表名称
    唯一索引:索引的值必须保证唯一,但允许有空值 。
    特点:有索引的属性的值不能出现重复的值
    语法: crate index unque 索引名称 on 表名称(字段名称)
    主键索引
    数据库默认使用innodb引擎 也就是说当你创建主键的时候数据库会默认的把你的
    主键设置为主键索引
    复合索引:一个索引包含多个列 INDEX Multildx( id name age)
    比如说有一学生表 经常的把学生表的name和 年龄作为条件去进行查询的话
    就可以把name和age这两个字段 创建一个复合索引
    语法 create index 索引名称 on 表名称(字段名称,字段名称)
    复合索引多个列组成大的索引
    注意:复合索引要遵循最左原则 也就是最佳左前缀法则(带头索引不能死,中间
    的索引不能断)
    全文索引:只有在MylSAM 引擎上才能使用 ,只能在C HAR ,VARCHAR ,TEXT 类型 字段上使用全文
    索引

    组合索引:(特点:用户可以在多个列上建立索引,复合索引在数据库操作期间所需的开销会更小,
    可以代替多个单一索引)
    空间索引: 空间索引是对空间数据类型的字段上建立的 索引

    索引类型:

    在这里插入图片描述 mysql的用的是 BTREE: 是B+TREE

    哈希表:

    哈希表(hash table 也叫散列表)是根据关键码值(key ,value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射 到表中一个位置来访问记录,以加快查找 的速度。这个映射函数叫做散列函数 存放记录的数组叫做散列表。
    哈希表hash table(key ,value) 的做法其实很简单,就是把key通过一个固定的算法函数既 所谓的哈希函数转换成一个整型的数字,然后就将该数字对数组长度进行取余 取余结果就当作数组的下标 将value存储在以该数字为标的数组空间里。
    而当使用哈希表进行查询的时候。就是再次使用key转换对应的数组下标,并定位改空间获取value 如此一来 就可以充分利用数组的定位性能进行数据定位
    在这里插入图片描述优点:查找可以直接key进行查找 查找效率高
    缺点:不能进行范围查找 而且只 支持MEMORY

    二叉树:

    二叉树 (Binary Search Tree , 简称BST)一颗相对平衡的有序二叉树,对其进行插入,查找,删除等操作 ,平均复杂度为O(logn)。
    它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。
    在这里插入图片描述
    在这里插入图片描述
    缺点: 是不平衡

    红黑树:

    在这里插入图片描述
    在这里插入图片描述
    缺点: 还是会左轻 不 平衡

    B+树:

    BTREE

    B+树,这里的 B 表示 balance(平衡的意思) ,B+ 树是一种多路;自平衡的搜索树
    它类似普通的平衡二叉树。
    真实的数据存在于叶子节点;非叶子节点 只不存储真实的数据,只存储指引搜索方向的数据项。
    在这里插入图片描述B树 或者B+树 中的节点为一页或页的倍数大小比较合适
    一个好的索引结构, 在使用它的过程中要有尽量少的磁盘I/o操作
    在这里插入图片描述
    优点:
    1:非叶子节点不存储数据, 叶子节点存储数据,一个非叶子节点内能存储更多的索引key,树的度变大 ,I/O效率更大
    2:叶子节点有指向相邻 叶子节点的指针,提高了范围查找的效率

    实现原理图B+树 (…):https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

    Mysql中的索引原理

    索引属于存储引擎级别的 的概念,这里分析的是MyISaM和innodb
    在这里插入图片描述

    MylsAM索引

    在这里插入图片描述
    总结:
    mylsAM中索引检索的算发为首先按照B+Tree 搜索算发搜索 索引,如果指定的key存在,则取出其他data的值 ,然后以data的值为地址 读取相应数据记录

    innoDB中的索引实现:
    在innoDB中 表数据文件本身就是按B+Tree组织的一个索引结构, 这颗树的叶节点data保存了完整的数据记录。
    在这里插入图片描述
    在这里插入图片描述
    聚集索引是指 数据库表行中数据的物理顺序与键值的逻辑(索引)顺序相同。一个表只能有一个聚集索引,因为一个表的物理顺序只有一种情况,所以,对应的聚集索引只能有一个,如果某索引不是聚集索引,则表中的行物理顺序与索引顺序不匹配,与非聚集索引相同,聚集索引有着更快的检索速度

    总结:
    首先检索辅助 索引获得主键,然后用主键到主键索引中检索获得 记录
    非聚集索引: (myisam 存储引擎的索引数据结构)
    就是索引和数据是分开的就是非聚集索引
    聚集索引: (innodb 存储引擎的索引的数据结构)
    *.ibd 文件 存放的表和数据,
    *.frm 文件 是表结构,
    就是数据和索引是在一块的就是聚集索引。
    特性:
    1:默认会拿主键去做索引,
    2:如果没有主键会拿一个非空的并且是唯一索引 来做聚集索引,
    3:如果以上没有 innodb 会自己维护一个id作为聚集索引。

    那些情况需要添加索引:

    在这里插入图片描述

    什么情况不适合索引:

    在这里插入图片描述
    索引 案例:
    给id 添上主键就是一个 mysql 会默认添加上一个唯一的索引。
    给字段 加索引:mimaindex
    在这里插入图片描述
    在这里插入图片描述

    create  index   indexName  ON  t_user(user_cod(20));
              --   indexName  创建索引名字
              --    t_user  给那个表加索引
              --    user_cod(20)  给那个字段加  长度是多少 
    
    

    在这里插入图片描述
    在这里插入图片描述

    特别的查询会导致索引失效 注意事项:

    1 :全值匹配最好
    2:最佳左前缀法则(带头索引不能死,中间的索引不能断)
    如果索引多个列,要遵守最佳左前缀法则。指的是查询从索引的最左前列开始 并且
    不跳过索引中的列
    3:不要在索引上做任何 操作(计算,函数, 自动/手动类型的转换)不然会导致索引失效而向全表扫描。
    4:MYSQL 储存的引擎不能继续使用索引中范围条件(bettween ,< ,> in 等)右边的列
    5:尽量使用覆盖索引(只查询索引的列 (索引列和查询列一致))。减少select
    6:索引字段上使用(!= 或者 <>) 判断时,会导致索引失效而转向 全表扫描。
    7:索引字段上使用 is null/ is not null 判断时,会导致索引失效而转向全表扫描。
    8:索引字段使用like以通配符开头(’%字符串‘)时,会导致索引失效而转向全表扫描
    由结果可知like 以通配符结束相当与范围 查找,索引不会失效,与范围条件(bettwween ,< > in 等) 不同的是不会导致右边的 索引消失。
    9:索引字段时字符串 但查询时 不加单引号 ,会导致索引失效 而扫描全表
    10:索引字段使用or 时,会导致索引失效 而扫描全盘。

    展开全文
  • MySQL索引类型 一、简介 MySQL目前主要有以下几种索引类型: 1.普通索引 2.唯一索引 3.主键索引 4.组合索引 5.全文索引 二、语句 CREATE TABLE table_name[col_name data type] [unique|fulltext][index|key]...

     

    MySQL索引类型

    一、简介

    MySQL目前主要有以下几种索引类型:
    1.普通索引
    2.唯一索引
    3.主键索引
    4.组合索引
    5.全文索引

    二、语句

    CREATE TABLE table_name[col_name data type]
    [unique|fulltext][index|key][index_name](col_name[length])[asc|desc]

    1.unique|fulltext为可选参数,分别表示唯一索引、全文索引
    2.index和key为同义词,两者作用相同,用来指定创建索引
    3.col_name为需要创建索引的字段列,该列必须从数据表中该定义的多个列中选择
    4.index_name指定索引的名称,为可选参数,如果不指定,默认col_name为索引值
    5.length为可选参数,表示索引的长度,只有字符串类型的字段才能指定索引长度
    6.asc或desc指定升序或降序的索引值存储

    三、索引类型

    1.普通索引
    是最基本的索引,它没有任何限制。它有以下几种创建方式:
    (1)直接创建索引

    CREATE INDEX index_name ON table(column(length))

    (2)修改表结构的方式添加索引

    ALTER TABLE table_name ADD INDEX index_name ON (column(length))

    (3)创建表的时候同时创建索引

    复制代码

    CREATE TABLE `table` (
        `id` int(11) NOT NULL AUTO_INCREMENT ,
        `title` char(255) CHARACTER NOT NULL ,
        `content` text CHARACTER NULL ,
        `time` int(10) NULL DEFAULT NULL ,
        PRIMARY KEY (`id`),
        INDEX index_name (title(length))
    )

    复制代码

    (4)删除索引

    DROP INDEX index_name ON table

    2.唯一索引
    与前面的普通索引类似,不同的就是:索引列的值必须唯一,但允许有空值。如果是组合索引,则列值的组合必须唯一。它有以下几种创建方式:
    (1)创建唯一索引

    CREATE UNIQUE INDEX indexName ON table(column(length))

    (2)修改表结构

    ALTER TABLE table_name ADD UNIQUE indexName ON (column(length))

    (3)创建表的时候直接指定

    复制代码

    CREATE TABLE `table` (
        `id` int(11) NOT NULL AUTO_INCREMENT ,
        `title` char(255) CHARACTER NOT NULL ,
        `content` text CHARACTER NULL ,
        `time` int(10) NULL DEFAULT NULL ,
        UNIQUE indexName (title(length))
    );

    复制代码

    3.主键索引
    是一种特殊的唯一索引,一个表只能有一个主键,不允许有空值。一般是在建表的时候同时创建主键索引:

    CREATE TABLE `table` (
        `id` int(11) NOT NULL AUTO_INCREMENT ,
        `title` char(255) NOT NULL ,
        PRIMARY KEY (`id`)
    );

    4.组合索引
    指多个字段上创建的索引,只有在查询条件中使用了创建索引时的第一个字段,索引才会被使用。使用组合索引时遵循最左前缀集合

    ALTER TABLE `table` ADD INDEX name_city_age (name,city,age); 

    5.全文索引
    主要用来查找文本中的关键字,而不是直接与索引中的值相比较。fulltext索引跟其它索引大不相同,它更像是一个搜索引擎,而不是简单的where语句的参数匹配。fulltext索引配合match against操作使用,而不是一般的where语句加like。它可以在create table,alter table ,create index使用,不过目前只有char、varchar,text 列上可以创建全文索引。值得一提的是,在数据量较大时候,现将数据放入一个没有全局索引的表中,然后再用CREATE index创建fulltext索引,要比先为一张表建立fulltext然后再将数据写入的速度快很多。
    (1)创建表的适合添加全文索引

    复制代码

    CREATE TABLE `table` (
        `id` int(11) NOT NULL AUTO_INCREMENT ,
        `title` char(255) CHARACTER NOT NULL ,
        `content` text CHARACTER NULL ,
        `time` int(10) NULL DEFAULT NULL ,
        PRIMARY KEY (`id`),
        FULLTEXT (content)
    );

    复制代码

    (2)修改表结构添加全文索引

    ALTER TABLE article ADD FULLTEXT index_content(content)

    (3)直接创建索引

    CREATE FULLTEXT INDEX index_content ON article(content)

    四、缺点

    1.虽然索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行insert、update和delete。因为更新表时,不仅要保存数据,还要保存一下索引文件。
    2.建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重,但如果你在一个大表上创建了多种组合索引,索引文件的会增长很快。
    索引只是提高效率的一个因素,如果有大数据量的表,就需要花时间研究建立最优秀的索引,或优化查询语句。

    五、注意事项

    使用索引时,有以下一些技巧和注意事项:
    1.索引不会包含有null值的列
    只要列中包含有null值都将不会被包含在索引中,复合索引中只要有一列含有null值,那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为null。
    2.使用短索引
    对串列进行索引,如果可能应该指定一个前缀长度。例如,如果有一个char(255)的列,如果在前10个或20个字符内,多数值是惟一的,那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。
    3.索引列排序
    查询只使用一个索引,因此如果where子句中已经使用了索引的话,那么order by中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作;尽量不要包含多个列的排序,如果需要最好给这些列创建复合索引。
    4.like语句操作
    一般情况下不推荐使用like操作,如果非使用不可,如何使用也是一个问题。like “%aaa%” 不会使用索引而like “aaa%”可以使用索引。
    5.不要在列上进行运算
    这将导致索引失效而进行全表扫描,例如

    SELECT * FROM table_name WHERE YEAR(column_name)<2017;

    6.不使用not in和<>操作

    参考http://blog.codinglabs.org/articles/theory-of-mysql-index.html

    摘要

    本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论。

    文章主要内容分为三个部分。

    第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

    第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

    第三部分根据上面的理论基础,讨论MySQL中高性能使用索引的策略。

    数据结构及算法基础

    索引的本质

    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

    我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

    看一个例子:

    图1

    图1展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

    虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的,原因会在下文介绍。

    B-Tree和B+Tree

    目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引,这一节先单纯从数据结构角度描述它们。

    B-Tree

    为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

    d为大于1的一个正整数,称为B-Tree的度。

    h为一个正整数,称为B-Tree的高度。

    每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。

    每个叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null 。

    所有叶节点具有相同的深度,等于树高h。

    key和指针互相间隔,节点两端是指针。

    一个节点中的key从左到右非递减排列。

    所有节点组成树结构。

    每个指针要么为null,要么指向另外一个节点。

    如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1)v(key1),其中v(key1)v(key1)为node的第一个key的值。

    如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym)v(keym),其中v(keym)v(keym)为node的最后一个key的值。

    如果某个指针在节点node的左右相邻key分别是keyikeyi和keyi+1keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)。

    图2是一个d=2的B-Tree示意图。

    图2

    由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。B-Tree上查找算法的伪代码如下:

    
     
    1. BTree_Search(node, key) {
    2. if(node == null) return null;
    3. foreach(node.key)
    4. {
    5. if(node.key[i] == key) return node.data[i];
    6. if(node.key[i] > key) return BTree_Search(point[i]->node);
    7. }
    8. return BTree_Search(point[i+1]->node);
    9. }
    10. data = BTree_Search(root, my_key);

    关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2)logd((N+1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logdN)O(logdN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。

     

    另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法,有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

    B+Tree

    B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

    与B-Tree相比,B+Tree有以下不同点:

    每个节点的指针上限为2d而不是2d+1。

    内节点不存储data,只存储key;叶子节点不存储指针。

    图3是一个简单的B+Tree示意。

    图3

    由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。

    一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下面讨论。

    带有顺序访问指针的B+Tree

    一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。

    图4

    如图4所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

    这一节对B-Tree和B+Tree进行了一个简单的介绍,下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。

    为什么使用B-Tree(B+Tree)

    上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

    B树

    为什么要B树

    磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

    为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

    简介

    这里的B树,也就是英文中的B-Tree,一个 m 阶的B树满足以下条件:

    1. 每个结点至多拥有m棵子树;
    2. 根结点至少拥有两颗子树(存在子树的情况下);
    3. 除了根结点以外,其余每个分支结点至少拥有 m/2 棵子树;
    4. 所有的叶结点都在同一层上;
    5. 有 k 棵子树的分支结点则存在 k-1 个关键码,关键码按照递增次序进行排列;
    6. 关键字数量需要满足ceil(m/2)-1 <= n <= m-1;

    举个栗子:

    B树上大部分的操作所需要的磁盘存取次数和B树的高度是成正比的,在B树中可以检查多个子结点,由于在一棵树中检查任意一个结点都需要一次磁盘访问,所以B树避免了大量的磁盘访问。

    操作

    既然是树,那么必不可少的操作就是插入和删除,这也是B树和其它数据结构不同的地方,当然了,还有必不可少的搜索,分享一个对B树的操作进行可视化的网址,它是由usfca提供的。

    假定对高度为h的m阶B树进行操作。

    插入

    新结点一般插在第h层,通过搜索找到对应的结点进行插入,那么根据即将插入的结点的数量又分为下面几种情况。

    • 如果该结点的关键字个数没有到达m-1个,那么直接插入即可;
    • 如果该结点的关键字个数已经到达了m-1个,那么根据B树的性质显然无法满足,需要将其进行分裂。分裂的规则是该结点分成两半,将中间的关键字进行提升,加入到父亲结点中,但是这又可能存在父亲结点也满员的情况,则不得不向上进行回溯,甚至是要对根结点进行分裂,那么整棵树都加了一层。

    其过程如下:

    删除

    同样的,我们需要先通过搜索找到相应的值,存在则进行删除,需要考虑删除以后的情况,

    • 如果该结点拥有关键字数量仍然满足B树性质,则不做任何处理;
    • 如果该结点在删除关键字以后不满足B树的性质(关键字没有到达ceil(m/2)-1的数量),则需要向兄弟结点借关键字,这有分为兄弟结点的关键字数量是否足够的情况。
      • 如果兄弟结点的关键字足够借给该结点,则过程为将父亲结点的关键字下移,兄弟结点的关键字上移;
      • 如果兄弟结点的关键字在借出去以后也无法满足情况,即之前兄弟结点的关键字的数量为ceil(m/2)-1,借的一方的关键字数量为ceil(m/2)-2的情况,那么我们可以将该结点合并到兄弟结点中,合并之后的子结点数量少了一个,则需要将父亲结点的关键字下放,如果父亲结点不满足性质,则向上回溯;
    • 其余情况参照BST中的删除。

    其过程如下:

    B+树

    为什么要B+树

    由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引,而B树则常用于文件索引。

    简介

    同样的,以一个m阶树为例:

    1. 根结点只有一个,分支数量范围为[2,m];
    2. 分支结点,每个结点包含分支数范围为[ceil(m/2), m];
    3. 分支结点的关键字数量等于其子分支的数量减一,关键字的数量范围为[ceil(m/2)-1, m-1],关键字顺序递增;
    4. 所有叶子结点都在同一层;

    操作

    其操作和B树的操作是类似的,不过需要注意的是,在增加值的时候,如果存在满员的情况,将选择结点中的值作为新的索引,还有在删除值的时候,索引中的关键字并不会删除,也不会存在父亲结点的关键字下沉的情况,因为那只是索引。

    B树和B+树的区别

    这都是由于B+树和B具有这不同的存储结构所造成的区别,以一个m阶树为例。

    1. 关键字的数量不同;B+树中分支结点有m个关键字,其叶子结点也有m个,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。
    2. 存储的位置不同;B+树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。
    3. 分支结点的构造不同;B+树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。
    4. 查询不同;B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

    主存存取原理

    目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

    图5

    从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

    主存的存取过程如下:

    当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

    写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

    这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

    磁盘存取原理

    上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

    图6是磁盘的整体结构示意图。

    图6

    一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

    图7是磁盘结构的示意图。

    图7

    盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

    当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

    局部性原理与磁盘预读

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

    当一个数据被用到时,其附近的数据也通常会马上被使用。

    程序运行期间所需要的数据通常比较集中。

    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

    B-/+Tree索引的性能分析

    到这里终于可以分析B-/+Tree索引的性能了。

    上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

    每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

    B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

    综上所述,用B-Tree作为索引结构效率是非常高的。

    而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

    上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

    dmax=floor(pagesize/(keysize+datasize+pointsize))dmax=floor(pagesize/(keysize+datasize+pointsize))

    floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

    这一章从理论角度讨论了与索引相关的数据结构与算法问题,下一章将讨论B+Tree是如何具体实现为MySQL中索引,同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

    MySQL索引实现

    在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

    MyISAM索引实现

    MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

    图8

    这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

    图9

    同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

    MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

    InnoDB索引实现

    虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

    第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

    图10

    图10是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

    第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图11为定义在Col3上的一个辅助索引:

    图11

    这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

    了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

    下一章将具体讨论这些与索引有关的优化策略。

     

     

    两种引擎索引的比较:

     

    B-/+Tree索引的性能优势: 一般使用磁盘I/O次数评价索引优劣。

    1.结合操作系统存储结构优化处理: mysql巧妙运用操作系统存储结构(一个节点分配到一个存储页中->尽量减少IO次数) & 磁盘预读(缓存预读->加速预读马上要用到的数据).

    2.B+Tree 单个节点能放多个子节点相同IO次数,检索出更多信息。

    3.B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。

    详解:Mysql设计利用了磁盘预读原理,将一个B+Tree节点大小设为一个页大小,在新建节点时直接申请一个页的空间,这样就能保证一个节点物理上存储在一个页里,加之计算机存储分配都是按页对齐的,这样就实现了每个Node节点只需要一次I/O操作。

    B-Tree索引、B+Tree索引: 单个节点能放多个子节点,查询IO次数相同(mysql查询IO次数最多3-5次-所以需要每个节点需要存储很多数据)

    B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。

    B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

    B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。

    dmax=floor(pagesize/(keysize+datasize+pointsize))


    Mysql 索引底层实现-MyISAM & InnoDB

    聚簇索引: 索引 和 数据文件为同一个文件。非聚簇索引: 索引 和 数据文件分开的索引。

    MyISAM & InnoDB 都使用B+Tree索引结构。但是底层索引存储不同,MyISAM 采用非聚簇索引,而InnoDB采用聚簇索引。 

    MyISAM索引原理:采用非聚簇索引-MyISAM myi索引文件和myd数据文件分离,索引文件仅保存数据记录的指针地址。叶子节点data域存储指向数据记录的指针地址。(底层存储结构: frm -表定义、 myi -myisam索引、 myd-myisam数据)

    MyISAM索引按照B+Tree搜索,如果指定的Key存在,则取出其data域的值,然后以data域值-数据指针地址去读取相应数据记录。辅助索引和主索引在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。MyISAM索引树如下:


    InnoDB优势:高扩展性,充分发挥硬件性能 Crash Safe、 支持事务、 可以在线热备份

    InnoDB特性:

    1. 事务支持(ACID)2. 扩展性优良 3. 读写不冲突 4. 缓存加速

    2. 功能组件: redo/undo &  异步IO &  MVCC & 行级别锁 & Page Cache(LRU)

    InnoDB物理存储结构如下图:


     

    InnoDB表空间管理

    InnoDB物理存储文件结构说明:

        InnoDB以表空间Tablespace(idb文件)结构进行组织,每个Tablespace 包含多个Segment段,每个段(分为2种段:叶子节点Segment&非叶子节点Segment), 一个Segment段包含多个Extent,一个Extent占用1M空间包含64个Page(每个Page 16k),InnoDB B-Tree 一个逻辑节点就分配一个物理Page,一个节点一次IO操作。,一个Page里包含很多有序数据Row行数据,Row行数据中包含Filed属性数据等信息。

    • 表空间(ibd文件)

    • 段(一个索引2段:叶子节点Segment & 非叶子节点Segment

    • Extent(1MB):一个Extent(1M) 包含64个 Page(16k),一个Page里包含很多有序行数据 , InnoDB B-Tree 一个逻辑节点就分配一个物理Page,一个节点一次IO操作。

    • Page(16KB)

    • Row

    • Field

    表插入数据扩展原理: 一次扩张一个Extent空间(1M),64个Page,按照顺序结构向每个page中插入顺序。

    InnoDB逻辑组织结构:

    InnoDB索引树结构

    每个索引一个B+树, 一个B+树节点 = 一个物理Page(16K)

    • 数据按16KB切片为Page 并编号, 编号可映射到物理文件偏移(16K * N), B+树叶子节点前后形成双向链表, 数据按主键索引聚簇, 二级索引叶节点存储主键值, 通过叶节点主键值回表查找数据。

    InnoDB索引原理: 

      采用聚簇索引- InnoDB数据&索引文件为一个idb文件,表数据文件本身就是主索引,相邻的索引临近存储。 叶节点data域保存了完整的数据记录(数据[除主键id外其他列data]+主索引[索引key:表主键id])。 叶子节点直接存储数据记录,以主键id为key,叶子节点中直接存储数据记录。(底层存储结构: frm -表定义、 ibd: innoDB数据&索引文件)

    注:由于InnoDB采用聚簇索引结构存储,索引InnoDB的数据文件需要按照主键聚集,因此InnoDB要求表必须有主键(MyISAM可以没有)。如果没有指定mysql会自动选择一个可以唯一表示数据记录的列作为主键,如果不存在这样的列,mysql自动为InnoDB表生成一个隐含字段(6个字节长整型)作为主键。 InnoDB的所有 辅助索引 都引用 数据记录的主键 作为data域。

      聚簇索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得数据记录主键,然后用主键到主索引中检索获得数据记录。InnoDB聚簇索引结构:


    索引查找流程:

    #1.索引精确查找: 确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过 二分查找找到记录或未命中。(select * from user_info where id = 23)

     

     

    #2.索引范围查找:读取根节点至内存, 确定索引定位条件id=18, 找到满足条件第一个叶节点

    , 顺序扫描所有结果, 直到终止条件满足id >=22 (select * from user_info where id >= 18 and id < 22)


     

     

     

    #3.全表扫描:直接读取叶节点头结点, 顺序扫描, 返回符合条件记录, 到最终节点结束

    (select * from user_info where name = 'abc')

     

    #4.二级索引查找

     

     

    Create table table_x(int id primary key, varchar(64) name,key sec_index(name) )

    • Select * from table_x where name = “d”;

    通过二级索引查出对应主键,拿主键回表查主键索引得到数据, 二级索引可筛选掉大量无效记录,提高效率

     

     

    展开全文
  • 本文转自互联网 本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看 ...本文是微信公众号【Java技术江湖】的《重新学习MySQL数据库》其中一篇,本文部分内容来源于网络,...
  • 在数据库中,如果索引太多,应用程序的性能可能会受到影响,如果索引太少,又会对查询性能产生影响。所以,我们要追求两者的一个平衡点,足够多的索引带来查询性能提高,又不因为索引过多导致修改数据等操作时负载过...
  • 说到索引,很多人都知道“索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址,...因为索引并不是关系模型的组成部分,因此不同的DBMS有不同的实现,我们针对MySQL数据库的实现进...
  • mysql数据库索引实现原理

    千次阅读 2019-06-01 21:27:11
    在介绍索引实现之前,我们先来了解下几种树的数据结构。 二叉搜索树 二叉搜索树有以下性质 1.每个节点有一个关键字 2.左右孩子至多有一个。 3.关键字大于左孩子,小于右孩子。 正因为二叉搜索树的特性,所以...
  • MySQL索引底层实现原理

    千次阅读 多人点赞 2019-01-13 17:18:08
    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。 我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能...
  • MySql索引实现原理

    千次阅读 2015-01-18 17:26:55
    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。 我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能...
  • MySql索引原理分析

    2019-03-30 12:02:56
    MySql索引原理分析 目录 MySql索引原理分析 什么是索引?为什么要有索引? MYSQL索引的分类 索引原理分析 最左前缀原则 什么是索引?为什么要有索引? 索引用于快速找出在某个列中有一特定值的行,不...
  • MySQL索引的本质,MySQL索引实现MySQL索引的数据结构
  • mysql索引实现原理

    万次阅读 多人点赞 2016-08-10 09:49:33
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常...
  • 理解MySQL索引的底层实现原理

    千次阅读 2019-05-21 00:17:36
    理解索引的特性 、索引的本质 、其他结构的问题 、B-Tree 和 B+Tree 、MySQL索引实现
  • MySQL索引的底层实现原理一、前言二、索引类型1、Hash索引2、BTree索引和B+Tree索引(1)BTree索引(2)B+Tree索引(3)B+Tree对比BTree有点:3、全文索引 一、前言 MySQL支持诸多存储引擎,而各种存储引擎对索引的...
  • mysql索引底层原理分析

    万次阅读 多人点赞 2018-09-23 00:01:40
    大家都知道索引的重要性,基本用法在上章《最全面的mysql索引知识大盘点》已分享过,本章主要是探索索引的底层实现原理。当然了,我们还是以mysql为基准进行探讨。 目录 前言:innodb和myisam的区别 1.物理磁盘...
  • MySQL 索引底层实现原理(B-tree、B+tree)

    千次阅读 2019-10-29 14:21:49
    文章目录理解索引的特性索引的本质其他结构的问题B-Tree 和 B+TreeMySQL索引实现MyISAM索引实现InnoDB索引实现 理解索引的特性 索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里 MySQL支持多种...
  • Mysql索引查找原理及调优1.1 常见查找方法举例1.1.1 顺序查找(linear search )1.1.2 二分查找1.1.3 二叉排序树查找1.1.4 哈希散列法(哈希表)1.2 MyISAM实现索引1.2.1 MyISAM实现索引 介绍1.2.2 MyISAM索引的原理图...
  • 索引是帮助Mysql高效获取数据的排好序的数据结构。 索引数据结构: 1、二叉树 2、红黑树 3、Hash表 4、B-Tree 例:如下面一张表 无索引: 查找 col2=89的数据,会进行全表扫描,从第一个开始往下面扫描,直到找到col...
  • MySQL索引实现 在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。 MyISAM索引实现 新建一张MyISAM引擎的表会生成三个文件,...
  • MySQL索引原理实现

    千次阅读 2019-04-12 20:24:20
    说到索引,很多人都知道“索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址,在...但是索引是怎么实现的呢?因为索引并不是关系模型的组成部分,因此不同的DBMS有不同的实现,...
  • Mysql索引原理

    千次阅读 2018-06-05 21:22:11
    Mysql索引类型及其特性普通索引 最基本的索引,它没有任何限制,也是我们大多数情况下用到的索引。–直接创建索引 CREATE INDEX index_name ON table(column(length)) –修改表结构的方式添加索引 ALTER TABLE ...
  • MySQL索引原理

    万次阅读 多人点赞 2016-02-02 20:53:39
    B+树索引是B+树在数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡(balance),而不是二叉(binary),因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉...
  • 我们主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。 MyISAM存储引擎 - 主键索引 MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。 下图是 MyISAM主键索引 的原理图: 假设...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,861
精华内容 33,544
关键字:

mysql索引实现原理

mysql 订阅