数据库索引_数据库索引原理 - CSDN
数据库索引 订阅
索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。如果想按特定职员的姓来查找他或她,则与在表中搜索所有的行相比,索引有助于更快地获取信息。索引的一个主要目的就是加快检索表中数据,亦即能协助信息搜索者尽快的找到符合限制条件的记录ID的辅助数据结构。 展开全文
索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。如果想按特定职员的姓来查找他或她,则与在表中搜索所有的行相比,索引有助于更快地获取信息。索引的一个主要目的就是加快检索表中数据,亦即能协助信息搜索者尽快的找到符合限制条件的记录ID的辅助数据结构。
信息
外文名
index
详    述
提高系统的性能
分    类
聚簇索引 非聚簇索引
中文名
数据库索引
目    的
加快对表中记录的查找或排序
优    点
迅速
数据库索引简介
索引是对数据库表中一个或多个列(例如,employee 表的姓名 (name) 列)的值进行排序的结构。例如这样一个查询:select * from table1 where id=10000。如果没有索引,必须遍历整个表,直到ID等于10000的这一行被找到为止;有了索引之后(必须是在ID这一列上建立的索引),即可在索引中查找。由于索引是经过某种算法优化过的,因而查找次数要少的多。可见,索引是用来定位的。从数据搜索实现的角度来看,索引也是另外一类文件/记录,它包含着可以指示出相关数据记录的各种记录。其中,每一索引都有一个相对应的搜索码,字符段的任意一个子集都能够形成一个搜索码。这样,索引就相当于所有数据目录项的一个集合,它能为既定的搜索码值的所有数据目录项提供定位所需的各种有效支持 [1]  。
收起全文
精华内容
参与话题
  • 什么是数据库索引,是怎么工作的?

    千次阅读 多人点赞 2018-02-25 19:48:46
    我们通过一个简单的例子来开始教程,解释为什么我们需要数据库索引。假设我们有一个数据库表 Employee, 这个表有三个字段(列)分别是 Employee_Name、Employee_Age 和Employee_Address。假设表Employee 有上千行...

    我们通过一个简单的例子来开始教程,解释为什么我们需要数据库索引。假设我们有一个数据库表 Employee, 这个表有三个字段(列)分别是 Employee_Name、Employee_Age 和Employee_Address。假设表Employee 有上千行数据。

    现在假设我们要从这个表中查找出所有名字是‘Jesus’的雇员信息。我们决定使用下面的查询语句:

    SELECT * FROM Employee 
    WHERE Employee_Name = 'Jesus'

    如果表中没有索引会发生什么?

    一旦我们运行这个查询,在查找名字为Jesus的雇员的过程中,究竟会发生什么?数据库不得不Employee表中的每一行并确定雇员的名字(Employee_Name)是否为 ‘Jesus’。由于我们想要得到每一个名字为Jesus的雇员信息,在查询到第一个符合条件的行后,不能停止查询,因为可能还有其他符合条件的行。所以,必须一行一行的查找直到最后一行-这就意味数据库不得不检查上千行数据才能找到所以名字为Jesus的雇员。这就是所谓的全表扫描

    数据库索引是怎样提升性能的?

    你可能会想为如此简单的事情做全表扫描效率欠佳-数据库是不是应该更聪明一点呢?这就像用人眼从头到尾浏览整张表-很慢也不优雅。但是,你可以能根据文章标题已经猜到,这就是索引派上用场的时候。使用索引的全部意义就是通过减少一张表中需要查询的记录/行的数目来加快搜索的速度。

    数据库索引是怎样提升性能的?

    索引是存储一张表中一个特定列的值的数据结构(最常见的是B-Tree)。索引是在表的列上创建。所以,要记住的关键点是索引包含一个表中列的值,并且这些值存储在一个数据结构中。请记住记住这一点:索引是一种数据结构 。

    什么样的数据结构可以作为索引?

    B-Tree 是最常用的用于索引的数据结构。因为它们是时间复杂度低, 查找、删除、插入操作都可以可以在对数时间内完成。另外一个重要原因存储在B-Tree中的数据是有序的。通常由数据库管理系统(RDBMS)决定索引应该用哪些数据结构。但是,在某些情况下,你在创建索引时可以指定索引要使用的数据结构。

    哈希表索引是怎么工作的?

    哈希表是另外一种你可能看到用作索引的数据结构-这些索引通常被称为哈希索引。使用哈希索引的原因是,在寻找值时哈希表效率极高。所以,如果使用哈希索引,对于比较字符串是否相等的查询能够极快的检索出相应的值。例如之前我们讨论过的这个查询(SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’) 就可以受益于创建在Employee_Name 列上的哈希索引。哈希索引的工作方式是将列的值通过hash算法计算出hash值,将其作为索引的键值(key),和键值相对应实际的值(value)是指向该表中相应行的指针。因为哈希表基本上可以看作是关联数组,一个典型的数据项就像“Jesus => 0x28939″,而0x28939是对内存中表中包含Jesus这一行的引用。在哈希索引的中查询一个像“Jesus”这样的值,并得到对应行的在内存中的引用,明显要比扫描全表获得值为“Jesus”的行的方式快很多。

    哈希索引的缺点

    哈希表是无序的数据结构,对于很多类型的查询语句哈希索引都无能为力。举例来说,假如你想要找出所有小于40岁的员工。你怎么使用使用哈希索引进行查询?这不可行,因为哈希表只适合查询键值对-也就是说查询相等的查询(例:WHERE name = ‘Jesus’)。哈希表的键值映射也暗示其键的存储是无序的。这就是为什么哈希索引通常不是数据库索引默认的数据结构-因为若将其作为索引的数据结构,并没有B-Tree那么灵活。

    还有什么其他类型的索引?

    使用R-Tree作为索引的数据结构通常用来为空间问题提供帮助。例如,一个查询要求“查询出所有距离我两公里之内的星巴克”,如果数据库表使用R- Tree索引,这类查询的效率将会提高。
    另一种索引是位图索引(bitmap index), 这类索引适合放在包含布尔值(true 和 false)的列上,但是这些值(表示true或false的值)的许多实例-基本上都是选择性(selectivity)低的列。

    索引是怎么提升性能的?

    因为索引基本上是用来存储列值的数据结构,这使查找这些列值更加快速。如果索引使用最常用的数据结构-B-Tree-那么其中的数据是有序的。有序的列值可以极大的提升性能。下面解释原因。

    假设我们在 Employee_Name这一列上创建一个B-Tree索引。这意味着当我们用之前的SQL查找姓名是‘Jesus’的雇员时,不需要再扫描全表。而是用索引查找去查找名字为‘Jesus’的雇员,因为索引已经按照按字母顺序排序。索引已经排序意味着查询一个名字会快很多,因为名字首字母为‘J’的员工都是排列在一起的。另外重要的一点是,索引同时存储了表中相应行的指针以获取其他列的数据。

    数据库索引里究竟存的是什么?

    你现在已经知道数据库索引是创建在表的某列上的,并且存储了这一列的所有值。但是,需要理解的重点是数据库索引并不存储这个表中其他列(字段)的值。举例来说,如果我们在Employee_Name列创建索引,那么列Employee_Age和Employee_Address上的值并不会存储在这个索引当中。如果我们确实把其他所有字段也存储在个这个索引中,那就成了拷贝一整张表做为索引-这样会占用太大的空间而且会十分低效。

    索引存储了指向表中某一行的指针

    如果我们在索引里找到某一条记录作为索引的列的值,如何才能找到这一条记录的其它值呢?这是很简单 - 数据库索引同时存储了指向表中的相应行的指针。指针是指一块内存区域, 该内存区域记录的是对硬盘上记录的相应行的数据的引用。因此,索引中除了存储列的值,还存储着一个指向列值在行数据的引用。也就是说,索引中的Employee_Name这列的某个值(或者节点)可以描述为 (“Jesus”, 0x82829), 0x82829 就是包含 “Jesus”那行数据在硬盘上的地址。如果没有这个引用,你就只能访问到一个单独的值(“Jesus”),而这样没有意义,因为你不能获取这一行记录的employee的其他值-例如地址(address)和年龄(age)。

    数据库怎么知道什么时候使用索引?

    当这个SQL (SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’ )运行时,数据库会检查在查询的列上是否有索引。假设Employee_Name列上确实创建了索引,数据库会接着检查使用这个索引做查询是否合理 - 因为有些场景下,使用索引比起全表扫描会更加低效。

    你能强制数据库使用索引吗?

    通常来说, 你不会告诉数据库什么时候使用索引 - 数据库自己决定。然而,值得注意的是在大多数数据库中(像Oracle 和 MySQL), 你实际上可以制订你想要使用的索引。

    如何在使用SQL创建索引

    之前的例子中,在Employee_Name列上创建索引的SQL如下:

    CREATE INDEX name_index
    ON Employee (Employee_Name)

    如何创建联合索引

    我们可以在雇员表上创建两个列的联合索引,SQL如下:

    CREATE INDEX name_index
    ON Employee (Employee_Name, Employee_Age)

    把数据库索引类比成什么比较好呢?

    一个非常好的类比是把数据库索引看作是书的索引。如果你有一本关于狗的书,你想要找关于‘黄金猎犬’的那部分。当你可以通过在书背的索引找到哪几页有关于‘黄金猎犬’信息的时候,你为什么要翻完整本书 - 这相当于数据库中的全表扫描。同样的,就像一本书的索引包含页码一样,数据库的索引包含了指针,指向你在SQL中想要查询的值所在的行。

    使用数据库索引会有什么代价?

    那么,使用数据库索引有什么缺点呢?其一,索引会占用空间 - 你的表越大,索引占用的空间越大。其二,性能损失(值更新操作),当你在表中添加、删除或者更新行数据的时候, 在索引中也会有相同的操作。记住:建立在某列(或多列)索引需要保存该列最新的数据

    基本原则是如果表中某列在查询过程中使用的非常频繁,那就在该列上创建索引。

    展开全文
  • 数据库的五种索引类型

    万次阅读 2019-03-15 21:24:13
    本文从如何建立mysql索引以及介绍mysql的索引类型,再讲mysql索引的利与弊,以及建立索引时需要注意的地方 首先:先假设有一张表,表的数据有10W条数据,其中有一条数据是nickname='css',如果要拿这条数据的话需要些的...

    本文从如何建立mysql索引以及介绍mysql的索引类型,再讲mysql索引的利与弊,以及建立索引时需要注意的地方

    首先:先假设有一张表,表的数据有10W条数据,其中有一条数据是nickname='css',如果要拿这条数据的话需要些的sql是 SELECT * FROM award WHERE nickname = 'css'

    一般情况下,在没有建立索引的时候,mysql需要扫描全表及扫描10W条数据找这条数据,如果我在nickname上建立索引,那么mysql只需要扫描一行数据及为我们找到这条nickname='css'的数据,是不是感觉性能提升了好多咧....

    mysql的索引分为单列索引(主键索引,唯索引,普通索引)和组合索引.

    单列索引:一个索引只包含一个列,一个表可以有多个单列索引.

    组合索引:一个组合索引包含两个或两个以上的列,

    本文使用的案例的表

    CREATE TABLE `award` (
       `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '用户id',
       `aty_id` varchar(100) NOT NULL DEFAULT '' COMMENT '活动场景id',
       `nickname` varchar(12) NOT NULL DEFAULT '' COMMENT '用户昵称',
       `is_awarded` tinyint(1) NOT NULL DEFAULT 0 COMMENT '用户是否领奖',
       `award_time` int(11) NOT NULL DEFAULT 0 COMMENT '领奖时间',
       `account` varchar(12) NOT NULL DEFAULT '' COMMENT '帐号',
       `password` char(32) NOT NULL DEFAULT '' COMMENT '密码',
       `message` varchar(255) NOT NULL DEFAULT '' COMMENT '获奖信息',
       `created_time` int(11) NOT NULL DEFAULT 0 COMMENT '创建时间',
       `updated_time` int(11) NOT NULL DEFAULT 0 COMMENT '更新时间',
       PRIMARY KEY (`id`)
     ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT='获奖信息表';

    复制代码

    (一)索引的创建

    1.单列索引

    1-1)    普通索引,这个是最基本的索引,

    其sql格式是 CREATE INDEX IndexName ON `TableName`(`字段名`(length)) 或者 ALTER TABLE TableName ADD INDEX IndexName(`字段名`(length))

    第一种方式 :

      CREATE INDEX account_Index ON `award`(`account`);

    第二种方式: 

    ALTER TABLE award ADD INDEX account_Index(`account`)

     

     

     

    如果是CHAR,VARCHAR,类型,length可以小于字段的实际长度,如果是BLOB和TEXT类型就必须指定长度,

    1-2)    唯一索引,与普通索引类似,但是不同的是唯一索引要求所有的类的值是唯一的,这一点和主键索引一样.但是他允许有空值,

    其sql格式是 CREATE UNIQUE INDEX IndexName ON `TableName`(`字段名`(length)); 或者 ALTER TABLE TableName ADD UNIQUE (column_list)  

    CREATE UNIQUE INDEX account_UNIQUE_Index ON `award`(`account`);

    1-3)    主键索引,不允许有空值,(在B+TREE中的InnoDB引擎中,主键索引起到了至关重要的地位)

    主键索引建立的规则是 int优于varchar,一般在建表的时候创建,最好是与表的其他字段不相关的列或者是业务不相关的列.一般会设为 int 而且是 AUTO_INCREMENT自增类型的

     

    2.组合索引

    一个表中含有多个单列索引不代表是组合索引,通俗一点讲 组合索引是:包含多个字段但是只有索引名称

    其sql格式是 CREATE INDEX IndexName On `TableName`(`字段名`(length),`字段名`(length),...);

     CREATE INDEX nickname_account_createdTime_Index ON `award`(`nickname`, `account`, `created_time`);

     

    如果你建立了 组合索引(nickname_account_createdTime_Index) 那么他实际包含的是3个索引 (nickname) (nickname,account)(nickname,account,created_time)

    在使用查询的时候遵循mysql组合索引的"最左前缀",下面我们来分析一下 什么是最左前缀:及索引where时的条件要按照建立索引的时候字段的排序方式

    1、不按索引最左列开始查询(多列索引) 例如index(‘c1’, ‘c2’, ‘c3’) where ‘c2’ = ‘aaa’ 不使用索引,where `c2` = `aaa` and `c3`=`sss` 不能使用索引

    2、查询中某个列有范围查询,则其右边的所有列都无法使用查询(多列查询)

    Where c1= ‘xxx’ and c2 like = ‘aa%’ and c3=’sss’ 改查询只会使用索引中的前两列,因为like是范围查询

    3、不能跳过某个字段来进行查询,这样利用不到索引,比如我的sql 是 

    explain select * from `award` where nickname > 'rSUQFzpkDz3R' and account = 'DYxJoqZq2rd7' and created_time = 1449567822; 那么这时候他使用不到其组合索引.

    因为我的索引是 (nickname, account, created_time),如果第一个字段出现 范围符号的查找,那么将不会用到索引,如果我是第二个或者第三个字段使用范围符号的查找,那么他会利用索引,利用的索引是(nickname),

    因为上面说了建立组合索引(nickname, account, created_time), 会出现三个索引

     

    (3)全文索引

    文本字段上(text)如果建立的是普通索引,那么只有对文本的字段内容前面的字符进行索引,其字符大小根据索引建立索引时申明的大小来规定.

    如果文本中出现多个一样的字符,而且需要查找的话,那么其条件只能是 where column lick '%xxxx%' 这样做会让索引失效

    .这个时候全文索引就祈祷了作用了

    ALTER TABLE tablename ADD FULLTEXT(column1, column2)

    有了全文索引,就可以用SELECT查询命令去检索那些包含着一个或多个给定单词的数据记录了。

    ELECT * FROM tablename
    WHERE MATCH(column1, column2) AGAINST(‘xxx′, ‘sss′, ‘ddd′)

    这条命令将把column1和column2字段里有xxx、sss和ddd的数据记录全部查询出来。

     

    (二)索引的删除

    删除索引的mysql格式 :DORP INDEX IndexName ON `TableName`

     

    (三)使用索引的优点

    1.可以通过建立唯一索引或者主键索引,保证数据库表中每一行数据的唯一性.
    2.建立索引可以大大提高检索的数据,以及减少表的检索行数
    3.在表连接的连接条件 可以加速表与表直接的相连 
    4.在分组和排序字句进行数据检索,可以减少查询时间中 分组 和 排序时所消耗的时间(数据库的记录会重新排序)
    5.建立索引,在查询中使用索引 可以提高性能

     

    (四)使用索引的缺点

    1.在创建索引和维护索引 会耗费时间,随着数据量的增加而增加
    2.索引文件会占用物理空间,除了数据表需要占用物理空间之外,每一个索引还会占用一定的物理空间
    3.当对表的数据进行 INSERT,UPDATE,DELETE 的时候,索引也要动态的维护,这样就会降低数据的维护速度,(建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重,但如果你在一个大表上创建了多种组合索引,索引文件的会膨胀很快)。

    (五)使用索引需要注意的地方

    在建立索引的时候应该考虑索引应该建立在数据库表中的某些列上面 哪一些索引需要建立,哪一些所以是多余的.
    一般来说,
    1.在经常需要搜索的列上,可以加快索引的速度
    2.主键列上可以确保列的唯一性
    3.在表与表的而连接条件上加上索引,可以加快连接查询的速度
    4.在经常需要排序(order by),分组(group by)和的distinct 列上加索引 可以加快排序查询的时间,  (单独order by 用不了索引,索引考虑加where 或加limit)
    5.在一些where 之后的 < <= > >= BETWEEN IN 以及某个情况下的like 建立字段的索引(B-TREE)

    6.like语句的 如果你对nickname字段建立了一个索引.当查询的时候的语句是 nickname lick '%ABC%' 那么这个索引讲不会起到作用.而nickname lick 'ABC%' 那么将可以用到索引

    7.索引不会包含NULL列,如果列中包含NULL值都将不会被包含在索引中,复合索引中如果有一列含有NULL值那么这个组合索引都将失效,一般需要给默认值0或者 ' '字符串

    8.使用短索引,如果你的一个字段是Char(32)或者int(32),在创建索引的时候指定前缀长度 比如前10个字符 (前提是多数值是唯一的..)那么短索引可以提高查询速度,并且可以减少磁盘的空间,也可以减少I/0操作.

    9.不要在列上进行运算,这样会使得mysql索引失效,也会进行全表扫描

    10.选择越小的数据类型越好,因为通常越小的数据类型通常在磁盘,内存,cpu,缓存中 占用的空间很少,处理起来更快

    (六)什么情况下不创建索引

    1.查询中很少使用到的列 不应该创建索引,如果建立了索引然而还会降低mysql的性能和增大了空间需求.
    2.很少数据的列也不应该建立索引,比如 一个性别字段 0或者1,在查询中,结果集的数据占了表中数据行的比例比较大,mysql需要扫描的行数很多,增加索引,并不能提高效率
    3.定义为text和image和bit数据类型的列不应该增加索引,
    4.当表的修改(UPDATE,INSERT,DELETE)操作远远大于检索(SELECT)操作时不应该创建索引,这两个操作是互斥的关系

     

     

     

    原文地址:https://www.cnblogs.com/chenshishuo/p/5030029.html

    展开全文
  • 数据库索引详解

    千次阅读 2017-04-09 11:22:13
    索引的重要性:当你的数据库的性能出现问题了,那么就重新优化你的索引吧,这能够解决80%的性能问题,由此可见索引的重要性,尤其在数据量越来越大的时候,影响更加的明显,一个最优的索引能够轻易的将查询性能提高...

    索引的重要性:当你的数据库的性能出现问题了,那么就重新优化你的索引吧,这能够解决80%的性能问题,由此可见索引的重要性,尤其在数据量越来越大的时候,影响更加的明显,一个最优的索引能够轻易的将查询性能提高好几个数量级

    索引的作用和优点:
    1. 能够大大的提高数据的查询检索速度
    2. 通过创建唯一性索引可以保证数据库中每一行的唯一性
    3. 可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。
    4. 在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。
    5. 通过使用索引,可以在查询的过程中,使用查询优化器,提高系统的性能。
    索引的弊端和缺点:
    1. 索引会占用一部分存储空间,尤其在数据量很大的时候占用的存储空间可是很客观的;
    2. 一旦对数据进行了插入、删除、修改等操作,要对索引进行动态的维护。

    但是总的来说利还是大于弊的,所以我们设计数据库的时候需要善于利用索引,善于优化索引。

    索引是最好的提高查询解决方案吗?
    答案: 不一定,只有当索引帮助存储引擎快速查找带来的好处大于其带来的额外开销时,索引才是有效的。
    对于非常小的表,大部分情况下全表扫描更加有效
    对于大中型的表,索引非常有效
    对于特大型的表,建立和维护索引的代价特别大,索引就不是那么有效了,可以使用分区技术,来进行一组数据的查询(而不是一条一条的匹配),对于更大的TB级别的数据,经常会使用块级别的元数据技术来代替索引,例如Infobright

    什么地方该用索引,什么地方应该避免使用索引?
    使用索引:
    1. 在数据量超过几百行之后就应该考虑建立索引,在主键上建立索引,保证数据的唯一性和组织表中的数据排列结构
    2. 在经常使用到的查询列上建立索引,比如 where name = “wang” ,经常做这样的查询,那么name上就应该建立索引
    3. 在经常进行范围查询的列上建立索引(可以建立聚簇索引,让索引的顺序和数据的物理存放顺序一致,这样大大的加快的查找的速度,变随机查找为顺序查找)
    4. 在经常用在连接的列上,在连接字段列上建立索引,这些列主要是一些外键,可以加快连接的速度;
    5. 在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间;
    不该使用索引
    1. 数据量太小不要建立索引,因为维护的代价要高于建立索引之后优化的代价
    2. 经常频繁更新的列不要建立索引,因为一旦更新,就要对索引也要随之更新,如果更新的代价比查询的代价高,那就不要建立索引
    3. 不经常被引用、查询的列不要建立索引,因为没有必要
    4. 对于那些列的取值很少(比如性别),或者text等类型的大文本字段不要建立索引,大文本字段的索引也会很长,影响查询

    使用索引注意事项:
    1. 对于复合索引,要选择合适的顺序建立索引,因为对于mysql来说,建立了字段 (A,B,C)的复合索引,其实实质上是建立了 索引 A,B,C 和索引A, 所以当你单独用 B 和C去查询的时候,索引并没有用到.
    在这里特别需要注意的是:索引的顺序非常重要!!!{
    不过不是按照索引的最左列开始查找,则无法使用索引, B 和C 不行
    不能跳过索引中的列, 利用A C查询无法使用索引
    如果查询中有某个列的范围,则右边的列无法使用索引查询优化,
    }
    2. order by中的列是不会使用索引的, 对于索引列排序, MySQL查询只使用一个索引,因此如果where子句中的列已经使用了索引的话,在数据库默认排序可以符合要求的情况下不要使用排序操作,所以如果可以的话,在经常order by的列上建立索引
    3. 一般情况下不鼓励使用like操作,如果非使用不可,如何使用也是一个问题。like “%aaa%” 不会使用索引,而like “aaa%”可以使用索引。
    4. 不要在列上进行计算,因为一旦出现了计算操作,将会导致该列不使用索引,而是直接全表扫描。
    5. 一些sql语句会导致不使用索引,而进行全表扫描,应该避免,比如:
    where 子句中不要对字段进行 null 值判断,否则将导致引擎放弃使用索引而进行全表扫描:select id from t where num is null (全表扫描) 修改成 select id from t where num is 0;
    where 字句中不要使用!=或<>操作符,否则将导致引擎放弃使用索引而进行全表扫描
    where 子句中不要使用 or 来连接条件,否则将导致引擎放弃使用索引而进行全表扫描,应该修改为使用 union 或者 union all (这两者的区别是 union 返回的是不重复的值,而union all 返回所有的每一列的值,包含重复元素 )
    select id from t where num=10 or num=20 全表扫描
    可以替换成:
    select id from t where num=10
    union all
    select id from t where num=20
    in 和 not in 也要慎用,否则会导致全表扫描 建议能用between替换,建议使用between, 另外用exists 替换也是很好的
    select num from a where num in(select num from b)
    用下面的语句替换:
    select num from a where exists(select 1 from b where num=a.num)
    注意的是 exists 实际上并不返回值,它只是检查exists 里面是否至少返回了一行数据,你可以理解为它返回一个true 或者false, 如果是那么where 语句就成立, 所以select 1你可以写成select 2,select id 都是没有任何问题的, 而in 确实会返回结果集的,所以in() 里面的字句必须返回的是num 字段集
    在列上对字段进行表达式操作,计算操作,函数操作,和使用参数都会导致全表扫描

    索引根据其构造结构可以分为 : B-tree索引, B+tree索引, Hash索引全文索引,空间数据索引(R-Tree),分行树索引(TokuDB中使用)
    先介绍几种树的概念:
    B树是二叉的排序树,也叫二叉查找树
    红黑树是B树的变种,是平衡的二叉排序树
    B-Tree 也是B树的改进,而不过二叉变成了多叉,而且非叶子节点中也存储了数据,搜索有可能到非叶结点就结束。
    B+Tree 是B-tree的变种,所有的关键字都出现在叶子节点上,一次查找搜索必然是到叶子节点上才结束的。
    B-tree 索引:
    B-tree 是一种平衡的多叉排序树,,,B-Tree它的特点如下:(M代表着阶数,代表着一个节点最多有多少个孩子节点,例如M阶B树代表着该B树的节点的孩子节点最多有M个
    1.定义任意非叶子结点最多只有M个儿子;且M>2;
    2.根结点的儿子数为[2, M];
    3.除根结点以外的非叶子结点的儿子数为[M/2, M];
    4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
    5 非叶子节点的关键字个数 = 指向儿子的指针个数 - 1
    6. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树
    7. 所有的叶子节点位于同一层

    B-Tree的特性:
    1. 关键字集合分布在整棵树中
    2. 任何关键字出现且只出现在一个节点中
    3. 搜索有可能在非叶子节点中结束
    4. 搜索性能等价于做二分查找,做一次查找最大的次数为 h 次,h为B-tree的深度

    在数据库中B-Tree索引的实现:
    1. 根节点常驻内存
    2. 根节点和非叶子节点的槽中存放了指向下一个子节点的指针,每个页中存放着一些关键字,与指针相对应,定义了子节点中值的上限与下限,存储引擎根据这些指针向下层查找, 但是叶子节点中只存放数据的物理地址,不再存放指针。
    3. 将每一个节点设定为一个页的大小,这样只需要一次I/O就可以读取一个节点的内容,(这是因为页是计算机管理存储器的逻辑块,硬件和操作系统在进行内存和磁盘上的数据交换时往往以一个页作为基本单位)
    4. 在叶节点和非叶子节点中,都存储了关键字(该关键字里包含了指向该索引数据本身的物理地址),在一次查找中,给定了某个关键字,如果在任何节点找到了该关键字(包括非叶结点)则就可以根据找到的关键字读取到该关键字所指向的实际数据。

    B+tree 索引: 是B-Tree的变种
    大部分的定义和B-Tree相同,但是它有独特于B-tree的地方,
    1. 非叶结点的子树指针和关键字个数相同
    2. 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间)
    3. 所有的叶子节点增加了一个指针,指针指向相邻的叶子节点。
    4. 所有的关键字都在叶子节点中出现

    B+Tree的特点
    1. 所有的关键字都出现在叶子节点中(稠密索引),而且叶子节点中的关键字恰好都是有序的
    2. 不可能在非叶子节点查找成功,这是因为非叶子节点中存储的仍旧是索引,并没有存储实际的数据或者指向实际数据的物理地址,在叶子节点才存放的是实际的数据或者实际数据的物理地址
    3. 查找方式有两种: 一种是从根节点进行查找,另一种是可以从叶子节点的开头开始查找,因为叶子节点中存储了指向下一个叶子节点的指针,而且在数据库的实现中,叶子节点在实际的物理存储中是顺序存放的,也就是叶子节点都是集中在一块存储区域内存放的(这样的好处是大大提高了区间查询效率)
    4. 更适合文件系统

    B+Tree 在 MySQL中的实现
    MySQL 中 的 InnoDB和MyISAM存储引擎使用的就是B+Tree的实现方案
    在InnoDB中,数据的物理存放顺序是按照设定聚簇索引的列的顺序进行组织的(实质上是按照主键的顺序组织数据),聚簇索引(一定包含主键,但也可能是主键和其他列的复合索引),对于InnoDB中来说,它的索引文件和数据文件是同一个文件,所以读取进来的页中(也就是一个节点)包含了key和data(key 为索引,data为实际的数据)
    {
    同时,对于聚簇索引来说, key = 索引键值;data = 实际数据本身
    对于非聚簇索引,key = 索引键值, data = 聚簇索引的值
    }
    所以了解了InnoDB的索引实现就可以很容易的理解为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大另外使用自增字段作为主键则是一个很好的选择,因为非递增的索引会在插入删除数据时候,为了维持B+Tree的特性而频繁的进行调整,十分低效

    对于MyISAM 存储引擎,按主键顺序储存数据,索引文件和数据文件是两个文件,会将索引文件读进内存,文件中的所有索引, key = 索引键值, data = 数据的物理地址 。

    MyISAM 和InnoDB中的索引比较
    1. MyisAM支持全文索引(FULLTEXT)、压缩索引,InnoDB不支持
    2. MyisAM 按主键顺序储存数据,主键索引叶子节点保存对应数据行物理地址,辅助索引跟主键索引相差无几;InnoDB 按聚簇索引顺序存储数据,聚簇索引同时保存数据行实际数据,其他辅助索引保存的是聚簇索引的值
    3. MyisAM键值分离,索引载入内存(key_buffer_size),数据缓存依赖操作系统; InnoDB键值一起保存,索引与数据一起载入InnoDB缓冲池; MyisAM主键(唯一)索引按升序来存储存储,InnoDB则不一定
    4. MyisAM处理字符串索引时用增量保存的方式,如第一个索引是‘preform’,第二个是‘preformence’,则第二个保存是‘7,ance’,这个明显的好处是缩短索引,但是缺陷就是不支持倒序提取索引,必须顺序遍历获取索

    B+Tree 和B-Tree的性能比较?
    1. 相对来说 ,B-Tree键值只在索引中出现一次,比B+Tree能节省存储空间
    2. B-Tree树的键值位置不定,使得在插入删除操作中复杂度明显增加,B+Tree的插入删除操作性能比B-Tree更好
    3. B+Tree因为叶子节点的物理存放是集中在一块存储区域的而且按顺序存放,所以 B+Tree进行区间查询的速度会更加的快

    先介绍一下局部性原理和磁盘预读:
    局部性原理: 当一个数据被用到时,其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中
    磁盘预读(目的就是要减少磁盘I/O,理论根据就是局部性原理): 由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。
    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。
    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行

    为什么选用B+/-Tree,而不是用红黑树(平衡二叉树)?
    上面介绍了在索引的实现中,是将每一个节点设置为一个页的大小来提高效率的,可知检索一次最多需要访问h个节点,需要h-1次磁盘I/O,O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。
    如果使用红黑树构件索引,那么树的深度H将会非常的大,O(h)=O(log2N),由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O需要h-1次,效率明显比B-Tree差很多。

    B-Tree的插入与删除请观看博客
    http://blog.csdn.net/hguisu/article/details/7786014

    插入:首先在最底层的节点中添加一个关键字,如果添加该关键字之后,满足M阶B树的条件(该节点关键字个数不超过M-1),则完成添加,否则就要对B树进行调整,具体的调整策略请看上面链接的博客。
    删除的时候,首先在最底层的节点删除那个关键字,删除之后,看是否满足M阶B树的条件(关键字数目不低于ceil(M/2) 向上取整),满足删除成功,不满足对树进行调整,调整策略请看上述博客。

    Hash索引:
    基于Hash表实现,只有精确匹配索引所有列的查询才会生效。
    Hash索引的优势:
    对于每一行,存储索引都会对所有的索引计算一个hash值,该值比较小,hash索引将每一行对应的hash值存储在hash索引中,也就是说hash表中存放了每一行的hash值,和该行的数据地址, 因此索引的结构非常紧凑,节省了存储空间,同时hash索引的查询速度非常的快
    Hash索引的局限:
    1. hash索引只包含哈希值和行指针,而不存储字段值,所以必须要实现读取行数据本身的操作
    2. hash索引不能用来进行范围查询(like,< >等),只支持等值查询
    3. hash索引也无法用来进行排序,因为它不是按照索引值的大小进行存储的
    4. 对于复合索引,不支持部分索引列匹配查找,比如在A,B,C上建立索引(hash值为ABC的联合值),所以单独查询A无法使用Hash索引
    5. 如何hash冲突很多的话,代价也比较大

    全文索引
    是一种特殊类型的索引,它查找的是文本中的关键词,而不是直接比较索引中的值,类似于搜索引擎做的事情。
    MyISAM中的全文索引是一类特殊的B-Tree索引,共有两层,第一层是所有的关键字,对于每一个关键字的第二层包含的是一组相关的文档指针,全文索引不会索引文档中的所有词语,会根据相关规则过滤掉一些词语,而且也不会存储关键字具体匹配在哪一行。
    因为MyISAM存储引擎的限制,多数情况下我们会选择InnoDB引擎 和 Sphinx插件来实现全文索引的功能。

    按照功能来划分: 索引可以分为两大类:
    主键索引,在主键上建立的索引,不允许空值null,每一行都是唯一的,一个表只有一个主键,主键可以作为外键
    定义了主键,会自动的为主键创建索引;
    唯一索引,索引的字段的值只能出现一次,可以为null,主键索引就是一种特殊的唯一索引,可以创建多个唯一索引
    CREATE UNIQUE INDEX index_name
    ON table_name (column_name)
    普通索引(简单索引)”允许使用重复的值,允许创建多个简单索引
    CREATE INDEX index_name
    ON table_name (column_name);
    复合索引,在多个列上建立的索引
    CREATE INDEX index_name
    ON table_name (column_name, column_name,….)
    前缀索引: 单列的前10个字符创建前缀索引,前缀索引用于解决要索引一个很长的字符列的情况,诀窍是选择合适长的前缀来保证较高的选择性(利用前缀就可以精确定位到一行要查询的数据),又不会太长造成创建或者维护索引的巨大开销。MySQL中对于Blob,Text,很长的varchar的列必须使用前缀索引
    CREATE INDEX index_name
    ON table_name (column_name(10));
    在创建表的时候创建主键索引,唯一索引,普通索引:
    CREATE TABLE IF NOT EXISTS ‘User’ (
    PRIMARY KEY (id),
    UNIQUE KEY forumid (forumid),
    KEY forumname (forumname),
    KEY realname (realname)

    聚簇索引(聚集索引)
    CREATE CLUSTERED INDEX index_name
    ON table_name (column_name);
    非聚簇索引:除聚簇索引外的其他索引都是非聚簇索引。

    下面详细的介绍一下聚簇索引。
    聚簇索引实质上是一种数据的存储方式,它将数据行和相邻的索引键值紧凑的存储在一起,所以一个表只能有一个聚簇索引,因为不可能将数据存放在两个位置。数据的物理存放顺序和索引的存放顺序是一致的。
    MySQL中InnoDB的聚簇索引的实现,对于InnoDB来说,该存储引擎默认以主键作为聚簇索引来组织存储数据,所以InnoDB无法显式的创建聚簇索引了。因此InnoDB如果没有定义主键,会选择一个唯一的非空索引代替,如果这也没有,会隐式的定义一个主键来作为聚簇索引。
    聚簇索引的优点:
    1. 把相关的数据保存在一起,减少了磁盘的I/O操纵
    2. 数据的访问更加快捷,它将索引和数据保存在一起,因此只要找到了索引值就找到了数据,不需要再次去读取。
    3. 使用覆盖索引扫描的查询可以直接使用节点中的主键值。
    聚簇索引的缺点:
    1. 聚簇索引的最大优势是减少了磁盘I/O和查询数据的时间,如果数据全部在内存,则优势很微弱了
    2. 插入速度严重依赖于插入顺序,按照主键的插入顺序是加载数据到InnoDb表中速度最快的方式(而且主键最好设置为一个自增的字段,这样主键的值是顺序的,每次在插入的时候都能够插入到表的最后面,如果主键不是自增的,那么在插入的时候新的行不一定比最后的一行的键值大,所以总需要为新的行寻找合适的位置,需要额外工作,这也是为什么建议使用自增主键的原因),但是也会产生问题,对于高并发的工作环境中,在InnoDB中按照主键顺序插入到表中会造成明显的锁的争用,因为有可能所有的插入操作都集中在主键的上界点,导致插入所需的间隙锁的竞争,或者增加一行数据,所有的插入操作集中在主键的下界点。
    3. 更新聚簇锁的代价很大,因为也要移动数据
    4. 会导致全表扫描变慢,尤其是行很稀疏或者由于页分裂导致数据存放不连续的时候
    5. 在InnoDB中,二级索引可能比想象中的更大,而且二级索引需要两次查询才能命中数据这是因为二级索引中存放的是主键的值,而不是指向行的物理地址。(二级索引之所以如此设计的原因是在InnoDB表中的数据进行了移动行或者数据也分裂时无需更新二级索引的这个指针)

    覆盖索引:如果一个索引中已经包含(或者说覆盖了)所有要查询的字段的值,我们就称之为覆盖索引,这样就可以直接使用索引来直接获取列的数据,而不再需要读取数据行的回表查询了。善用覆盖索引能提高查询速度。

    explain 解析器: 分析sql语句的查询性能情况,分析select的查询行为
    关于这个解释器参数的详细说明,可以参考博客
    http://blog.csdn.net/leileixiaoshan/article/details/26108427

    我在这里只做一个简要的概括说明:
    id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
    +—-+————-+————–+——+—————+——+———+——+———+————-+
    | 1 | SIMPLE | TradeBalance | ALL | NULL | NULL | NULL | NULL | 3418948 | Using where

    id:表示查询语句中的查询顺序(select 语句中可能有子查询),id越大,说明越早执行

    select_type: 每个select字句的查询类型, 简单或者复杂,
    SIMPLE: 代表不包含子查询或者Union
    PRIMARY,SUBQUERY 包含子查询,最外层的标记为PRIMARY ,子查询标记为SUBQUERY
    UNION:第二个select语句出现在Union之后,标记为Union
    DERIVED:在From列表中包含的子查询
    UNION RESULT:从UNION表获取结果的SELECT

    table: 查询的表的名字

    type(这个属性很重要): 访问类型,表示MySQL在表中找到所需行的方式, 从上到下,性能由最差到最好
    ALL: 全表查询,遍历全表找到匹配行‘
    index:利用索引进行索引的遍历查询
    range 索引范围扫描, 对索引的扫描开始于某一点,返回匹配的行,常见于between,<, >
    ref: 非唯一性索引扫描, 返回匹配某个单独值的所有行, 常见于 =
    eq_ref: 唯一性索引扫描, 返回匹配的唯一一行,常见于主键或者唯一索引扫描
    const、system,查询对某部分进行优化,并且转换为一个常量时,system表示查询的表只有一行的特殊情况
    null: MySqL在优化过程中分解语句,执行甚至不用访问表或者索引
    possible_keys, 是指查询可能使用到的索引,key,表示查询实际使用到的索引, key_len表示索引字段可能的最大长度

    ref: 上述表的连接匹配条件,即哪些列或常量被用于查找索引列上的值
    rows: 找到所需的记录所需要读取的行数,也就是符合匹配条件的行数
    Extra,额外的信息
    Using index: 表示在select操作中用到了覆盖索引(Covering index)
    Using where: 表示MySqL使用where字句来过滤结果集,而且是先返回行结果集以后再使用where语句过滤行
    Using temporary : 表示需要使用到临时表来存储结果集,常用于排序和分组
    Using filesort 表示无法利用索引进行排序的操作称为文件排序
    MySQL执行计划的局限

    •EXPLAIN**不会告诉你关于触发器、存储过程的信息或用户自定义函数对查询的影响情况**
    EXPLAIN不考虑各种Cache
    EXPLAIN不能显示MySQL在执行查询时所作的优化工作
    •部分统计信息是估算的,并非精确值
    EXPALIN只能解释SELECT操作,其他操作要重写为SELECT后查看执行计划

    高性能的索引策略要考虑如下方面:
    1. 独立的列,即查询的的时候列中不存在计算,表达式,函数参数等
    2. 对于索引长字符列(blob,Text,),善于使用前缀索引
    3. 要选择合适的索引顺序,按照经验来说,选择性较高的字段放在前面,也就是说经过第一个条件之后得到的行数会比较的少
    4. 善于使用聚簇索引,在innoDb中按照主键顺序插入行
    5. 善于利用覆盖索引
    6. 利用索引扫描来做排序
    7. 可以使用压缩索引
    8. 移除或者优化重复和冗余索引,对于未使用的索引要删除掉
    9. 索引和锁,索引可以减少innoDB访问行的行数,从而减少对行的加锁,使用了索引之后,索引会过滤掉一些无效的行,从而使得只对有效的行进行加锁,需要注意的是,有时即使使用了索引也会锁住一些无效的行:
    select id from user where id <5 and id >1; 有时对于这种范围查询的时候也会锁住一些无效的行,首先结果会返回 id<5 的所有行,然后加锁, 然后再从结果中找 >1的结果返回,然后再解锁。
    由此可见,如果不使用索引,就会对全表扫描而锁住所有的行,开销特别大。

    此博文参考了博客
    http://blog.csdn.net/superhosts/article/details/25611119
    http://blog.csdn.net/leileixiaoshan/article/details/26108427

    展开全文
  • 数据库索引的实现原理

    万次阅读 多人点赞 2012-05-03 17:27:00
    数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种...

    强烈建议参阅链接:http://www.linezing.com/blog/?p=798#nav-1


    说白了,索引问题就是一个查找问题。。。


    数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树

    在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

    为表设置索引要付出代价的:一是增加了数据库的存储空间二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)


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


    创建索引可以大大提高系统的性能。

    第一,通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。

    第二,可以大大加快数据的检索速度,这也是创建索引的最主要的原因。

    第三,可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。

    第四,在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。

    第五,通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。 


    也许会有人要问:增加索引有如此多的优点,为什么不对表中的每一个列创建一个索引呢?因为,增加索引也有许多不利的方面。

    第一,创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。

    第二,索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要的空间就会更大。

    第三,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。


    索引是建立在数据库表中的某些列的上面。在创建索引的时候,应该考虑在哪些列上可以创建索引,在哪些列上不能创建索引。一般来说,应该在这些列上创建索引:在经常需要搜索的列上,可以加快搜索的速度;在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构;在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度;在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的;在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间;在经常使用在WHERE子句中的列上面创建索引,加快条件的判断速度。


    同样,对于有些列不应该创建索引。一般来说,不应该创建索引的的这些列具有下列特点:

    第一,对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为,既然这些列很少使用到,因此有索引或者无索引,并不能提高查询速度。相反,由于增加了索引,反而降低了系统的维护速度和增大了空间需求。

    第二,对于那些只有很少数据值的列也不应该增加索引。这是因为,由于这些列的取值很少,例如人事表的性别列,在查询的结果中,结果集的数据行占了表中数据行的很大比例,即需要在表中搜索的数据行的比例很大。增加索引,并不能明显加快检索速度。

    第三,对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。

    第四,当修改性能远远大于检索性能时,不应该创建索引。这是因为,修改性能和检索性能是互相矛盾的。当增加索引时,会提高检索性能,但是会降低修改性能。当减少索引时,会提高修改性能,降低检索性能。因此,当修改性能远远大于检索性能时,不应该创建索引。


    根据数据库的功能,可以在数据库设计器中创建三种索引:唯一索引、主键索引和聚集索引

    唯一索引 

    唯一索引是不允许其中任何两行具有相同索引值的索引。

    当现有数据中存在重复的键值时,大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如,如果在employee表中职员的姓(lname)上创建了唯一索引,则任何两个员工都不能同姓。
    主键索引
    数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。
    在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。
    聚集索引
    在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。

    如果某索引不是聚集索引,则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比,聚集索引通常提供更快的数据访问速度。



    局部性原理与磁盘预读

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘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)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

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


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



    应该花时间学习B-树和B+树数据结构

    =============================================================================================================

    1)B树

    B树中每个节点包含了键值和键值对于的数据对象存放地址指针,所以成功搜索一个对象可以不用到达树的叶节点。

    成功搜索包括节点内搜索和沿某一路径的搜索,成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。

    在B树中查找给定关键字的方法是:首先把根结点取来,在根结点所包含的关键字K1,…,kj查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查的关键字在某个Ki或Ki+1之间,于是取Pi所指的下一层索引节点块继续查找,直到找到,或指针Pi为空时查找失败。

    2)B+树

    B+树非叶节点中存放的关键码并不指示数据对象的地址指针,非也节点只是索引部分。所有的叶节点在同一层上,包含了全部关键码和相应数据对象的存放地址指针,且叶节点按关键码从小到大顺序链接。如果实际数据对象按加入的顺序存储而不是按关键码次数存储的话,叶节点的索引必须是稠密索引,若实际数据存储按关键码次序存放的话,叶节点索引时稀疏索引。

    B+树有2个头指针,一个是树的根节点,一个是最小关键码的叶节点。

    所以 B+树有两种搜索方法:

    一种是按叶节点自己拉起的链表顺序搜索。

    一种是从根节点开始搜索,和B树类似,不过如果非叶节点的关键码等于给定值,搜索并不停止,而是继续沿右指针,一直查到叶节点上的关键码。所以无论搜索是否成功,都将走完树的所有层。

    B+ 树中,数据对象的插入和删除仅在叶节点上进行。

    这两种处理索引的数据结构的不同之处:
    a,B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。
    b,因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
    c,B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。


    展开全文
  • 数据库索引

    万次阅读 多人点赞 2019-02-22 09:18:43
    数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询,更新数据库中表的数据.索引的实现通常使用B树和变种的B+树(mysql常用的索引就是B+树) 除了数据之外,数据库系统还维护为满足特定查找算法的数据...
  • 数据库索引简介

    2019-04-17 14:29:11
    建立的索引只对该字段有用,如果查询的字段改变,那么这个索引也就无效了,比如图书馆的书是按照书名的第一个字母排序的,那么你想要找作者叫张三的就不能用该索引了; 如果索引太多也会降低查询的速度 3、索引是...
  • 数据库索引原理,及MySQL索引类型

    万次阅读 多人点赞 2018-08-31 21:08:40
    MySQL索引类型一览 让MySQL高效运行起来 本文介绍了七种MySQL索引类型。在数据库表中,对字段建立索引可以大大提高查询速度。通过善用这些索引,可以令MySQL的查询和运行更加高效。 索引是快速搜索的关键。MySQL...
  • 了解数据库索引及其原理

    万次阅读 多人点赞 2018-06-25 16:10:30
    索引这个词相信对于一个开发猿来说,就好比看到我们的代码一样低头不见抬头见,在一些日常优化我们查询效率的方案中,不光考虑优化我们的sql语句,另外就是使用索引。使用索引很简单,只要能写创建表的语句,就肯定...
  • 数据库索引原理 b树

    千次阅读 2018-05-17 09:49:38
    1 .B-树定义B-树是一种平衡的多路查找树,它在文件系统中很有用。定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:⑴树中每个结点至多有m 棵子树;⑵若根结点不是叶子结点,则至少有两棵子树;...
  • 数据库索引到底是什么,是怎样工作的?

    万次阅读 多人点赞 2016-05-19 16:39:35
    我们通过一个简单的例子来开始教程,解释为什么我们需要数据库索引。假设我们有一个数据库表 Employee, 这个表有三个字段(列)分别是 Employee_Name、Employee_Age 和Employee_Address。假设表Employee 有上千行...
  • 下面是关于数据库索引的相关知识: 简单来说,数据库索引就是数据库的数据结构!进一步说则是该数据结构中存储了一张表中某一列的所有值,也就是说索引是基于数据表中的某一列创建的。总而言之:一个索引是由表中...
  • 数据库索引常见四种类型

    万次阅读 2019-03-19 13:02:42
    索引分四类: index ----普通的索引,数据可以重复 fulltext----全文索引,用来对大表的文本域(char,varchar,text)进行索引。语法和普通索引一样。 unique ----唯一索引,唯一索引,要求所有记录都唯一 primary ...
  • 索引的几种类型分别是普通索引、唯一索引、聚集索引、主键索引、全文索引几种。 使用索引的优点: 提高数据的搜索速度 加快表与表之间的连接速度 在信息检索过程中,若使用分组及排序子句进行时,通过建立索引能...
  • 数据库创建索引的几种方法

    万次阅读 2018-11-09 10:46:26
    1、普通索引  CREATE INDEX indexName ON mytable(username(length));  创建表的时候直接指定:  CREATE TABLE mytable(  ID INT NOT NULL,   username VARCHAR(16) NOT NULL,   INDEX [indexName] (.....
  • 数据库索引类型及实现方式

    万次阅读 2017-07-12 18:43:23
    数据库索引类型及实现方式 1、索引定义  数据库索引好比是一本书前面的目录,能加快数据库的查询速度。索引是对数据库表中一个或多个列(例如,employee 表的姓氏 (lname) 列)的值进行排序的结构。如果想...
  • MYSQL数据库四种索引类型的简单使用

    万次阅读 2017-09-18 13:43:34
    MYSQL数据库索引类型包括普通索引,唯一索引,主键索引与主键索引,这里对这些索引的做一些简单描述: (1)普通索引 这是最基本的MySQL数据库索引,它没有任何限制。它有以下几种创建方式: 创建索引 CREATE ...
  • mysql数据库创建索引和使用

    千次阅读 2018-11-08 13:43:46
    1. 2 ...需要注意索引需要的不同数据库引擎 alter table user add fulltext(字段名); 创建语句: CREATE TABLE zy_article( art_id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT, typ...
  • 数据库中的索引技术——哈希索引

    万次阅读 多人点赞 2018-09-09 21:46:09
    数据库中的索引技术——哈希索引 1、哈希索引 哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是...
  • 数据库常见面试题(附答案)

    万次阅读 多人点赞 2020-05-23 15:19:22
    2.数据库隔离级别,每个级别会引发什么问题,mysql默认是哪个级别 脏读:事务B读取事务A还没有提交的数据 不可重复读:两次事务读的数据不一致 幻读:事务A修改了数据,事务B也修改了数据,这时在事务A看
  • 数据库索引失效(原因)

    千次阅读 2018-07-22 00:13:46
    容易引起oracle索引失效的原因很多: 1、在索引列上使用函数。如SUBSTR,DECODE,INSTR等,对索引列进行运算.需要建立函数索引就可以解决了。 2、新建的表还没来得及生成统计信息,分析一下就好了 3、基于cost的...
1 2 3 4 5 ... 20
收藏数 662,040
精华内容 264,816
关键字:

数据库索引