浅谈数据库索引的作用及原理

数据库索引是为了增加查询速度而对表字段附加的一种标识。很多人机械的理解索引的概念，认为增加索引只有好处没有坏处。其实远不是那样的，这里将其介绍尽量详细些。

首先明白为什么索引会增加速度，DB在执行一条Sql语句的时候，默认的方式是根据搜索条件进行全表扫描，遇到匹配条件的就加入搜索结果集合。如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少遍历匹配的行数，所以能明显增加查询的速度。那么在任何时候都应该加索引么？这里有几个反例：1、如果每次都需要取到所有表记录，无论如何都必须进行全表扫描了，那么是否加索引也没有意义了。2、对非唯一的字段，例如“性别”这种大量重复值的字段，增加索引也没有什么意义。3、对于记录比较少的表，增加索引不会带来速度的优化反而浪费了存储空间，因为索引是需要存储空间的，而且有个致命缺点是对于update/insert/delete的每次执行，字段的索引都必须重新计算更新。

那么在什么时候适合加上索引呢？我们看一个Mysql手册中举的例子，这里有一条sql语句：

SELECT c.companyID, c.companyName FROM Companies c, User u WHERE c.companyID = u.fk_companyID AND
c.numEmployees >= 0 AND c.companyName LIKE '%i%' AND u.groupID IN (SELECT g.groupID FROM Groups g WHERE
g.groupLabel = 'Executive')

这条语句涉及3个表的联接，并且包括了许多搜索条件比如大小比较，Like匹配等。在没有索引的情况下Mysql需要执行的扫描行数是77721876行。而我们通过在companyID和groupLabel两个字段上加上索引之后，扫描的行数只需要134行。在Mysql中可以通过Explain Select来查看扫描次数。可以看出来在这种联表和复杂搜索条件的情况下，索引带来的性能提升远比它所占据的磁盘空间要重要得多。

那么索引是如何实现的呢？大多数DB厂商实现索引都是基于一种数据结构——B树。因为B树的特点就是适合在磁盘等直接存储设备上组织动态查找表。B树的定义是这样的：一棵m(m>=3)阶的B树是满足下列条件的m叉树：

1、每个结点包括如下作用域(j, p0, k1, p1, k2, p2, ... ki, pi) 其中j是关键字个数，p是孩子指针

2、所有叶子结点在同一层上，层数等于树高h

3、每个非根结点包含的关键字个数满足[m/2-1]<=j<=m-1

4、若树非空，则根至少有1个关键字，若根非叶子，则至少有2棵子树，至多有m棵子树

看一个B树的例子，针对26个英文字母的B树可以这样构造：

可以看到在这棵B树搜索英文字母复杂度只为o(m)，在数据量比较大的情况下，这样的结构可以大大增加查询速度。然而有另外一种数据结构查询的虚度比B树更快——散列表。Hash表的定义是这样的：设所有可能出现的关键字集合为u，实际发生存储的关键字记为k，而|k|比|u|小很多。散列方法是通过散列函数h将u映射到表T[0,m-1]的下标上，这样u中的关键字为变量，以h为函数运算结果即为相应结点的存储地址。从而达到可以在o(1)的时间内完成查找。

然而散列表有一个缺陷，那就是散列冲突，即两个关键字通过散列函数计算出了相同的结果。设m和n分别表示散列表的长度和填满的结点数，n/m为散列表的填装因子，因子越大，表示散列冲突的机会越大。

因为有这样的缺陷，所以数据库不会使用散列表来做为索引的默认实现，Mysql宣称会根据执行查询格式尝试将基于磁盘的B树索引转变为和合适的散列索引以追求进一步提高搜索速度。

总结

本文关于数据库索引的作用和原理就介绍到这里，希望对大家有所帮助。感兴趣的朋友可以参阅：oracle数据库导入TXT文件方法介绍  oracle 数据库启动阶段分析  oracle 虚拟专用数据库详细介绍 等。有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • Oracle数据库中建立索引的基本方法讲解

    怎样建立最佳索引? 1.明确地创建索引 create index index_name on table_name(field_name) tablespace tablespace_name pctfree 5 initrans 2 maxtrans 255 storage ( minextents 1 maxextents 16382 pctincrease 0 ); 2.创建基于函数的索引 常用与UPPER.LOWER.TO_CHAR(date)等函数分类上,例: create index

  • PHP以指定字段为索引返回数据库所取的数据数组

    很多情况下,我们从接触一个新的项目到开发完成,再回过头来仔细浏览一下自己写的代码,很多都是我们以前用熟练的代码.所以,在完成每个新项目的时 候,适当的做些项目总结.代码总结,或许你会在以后的项目中用得着,极有可能获得意外的收获,比如:代码优化,想到了更好.速度更快的实现方法等等. 牛逼的程序开发者有时候不在于代码量的多少,而是程序的代码简洁性.逻辑复杂但实现的方便性,这些才说明是否是一位好的程序员.我们不做日夜加班到深夜,拼代码量的程序员! 这篇和大家分享几个使用得PHP编程技巧,有些技巧是在看

  • mysql数据库索引损坏及修复经验分享

    mysql表索引被破坏的问题及解决 下午上班,惊闻我的dedecms的网站出问题了,访问一看,果然全屏报错,检查mysql日志,错误信息为: Table '.\dedecmsv4\dede_archives' is marked as crashed and should be repaired 提示说cms的文章表dede_archives被标记有问题,需要修复.于是赶快恢复历史数据,上网查找原因.最终将问题解决.解决方法如下: 找到mysql的安装目录的bin/myisamchk工具,在命令

  • 基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    B-树 1 .B-树定义 B-树是一种平衡的多路查找树,它在文件系统中很有用. 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:⑴树中每个结点至多有m 棵子树:⑵若根结点不是叶子结点,则至少有两棵子树: ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树:⑷所有的非终端结点中包含以下信息数据: (n,A0,K1,A1,K2,-,Kn,An)其中:Ki(i=1,2,-,n)为关键码,且Ki<Ki+1, Ai 为指向子树根结点的指针(i=0,1,-,n),且指针Ai-1 所指子

  • 什么是数据库索引 有哪些类型和特点

    什么是数据库索引 有哪些类型和特点

    有效优化VPS性能,提高VPS服务器运行速度,除了合理配置WEB服务器外,更多的是需要我们能够很好的优化网站程序及网站数据库,网站数据库的优化最为基础的优化措施就是建立数据库索引了,这里就介绍一下,什么是数据库索引?有哪些类型和特点? ⑴,什么是数据库索引? 数据库索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息.在数据库中,索引的含义与日常意义上的"索引"一词并无多大区别(想想小时候查字典),它是用于提高数据库表数据访问速度的数据库对象. ①

  • oracle数据库索引失效

    今天一个同事突然问我索引为什么失效.说实在的,失效的原因有多种: 但是如果是同样的sql如果在之前能够使用到索引,那么现在使用不到索引,以下几种主要情况: 1. 随着表的增长,where条件出来的数据太多,大于15%,使得索引失效(会导致CBO计算走索引花费大于走全表) 2. 统计信息失效      需要重新搜集统计信息 3. 索引本身失效      需要重建索引 下面是一些不会使用到索引的原因 索引失效 1) 没有查询条件,或者查询条件没有建立索引 2) 在查询条件上没有使用引导列 3) 查询

  • 浅谈数据库索引的作用及原理

    数据库索引是为了增加查询速度而对表字段附加的一种标识.很多人机械的理解索引的概念,认为增加索引只有好处没有坏处.其实远不是那样的,这里将其介绍尽量详细些. 首先明白为什么索引会增加速度,DB在执行一条Sql语句的时候,默认的方式是根据搜索条件进行全表扫描,遇到匹配条件的就加入搜索结果集合.如果我们对某一字段增加索引,查询时就会先去索引列表中一次定位到特定值的行数,大大减少遍历匹配的行数,所以能明显增加查询的速度.那么在任何时候都应该加索引么?这里有几个反例:1.如果每次都需要取到所有表记录,无论

  • 浅谈C++中虚函数实现原理揭秘

    编译器到底做了什么实现的虚函数的晚绑定呢?我们来探个究竟. 编译器对每个包含虚函数的类创建一个表(称为V TA B L E).在V TA B L E中,编译器放置特定类的虚函数地址.在每个带有虚函数的类 中,编译器秘密地置一指针,称为v p o i n t e r(缩写为V P T R),指向这个对象的V TA B L E.通过基类指针做虚函数调 用时(也就是做多态调用时),编译器静态地插入取得这个V P T R,并在V TA B L E表中查找函数地址的代码,这样就能调用正确的函数使晚捆绑发生

  • 浅谈SSH框架中spring的原理

    在ssh项目中,是有明确分工的,spring的作用就相当于将struts和hibernate连接起来,是将两个没有关系的框架的特性,方法,action都放在spring的配置文件中使他们建立关系.取他门各自所长.而这些做法他们自己不知道,他们是听命于spring调度的,他的的任务只是做好自己的事情. 这样做的好处就是任务结构分明,struts只管理显示与做什么,hibernate只关心怎么做,而spring就相当于领导,所以一切的类都要交给spring的工厂创建,这是一种良好的开发模式,体现了一

  • 浅谈HTTP使用BASIC认证的原理及实现方法

    一．BASIC认证概述 在HTTP协议进行通信的过程中,HTTP协议定义了基本认证过程以允许HTTP服务器对WEB浏览器进行用户身份证的方法,当一个客户端向HTTP服务 器进行数据请求时,如果客户端未被认证,则HTTP服务器将通过基本认证过程对客户端的用户名及密码进行验证,以决定用户是否合法.客户端在接收到HTTP服务器的身份认证要求后,会提示用户输入用户名及密码,然后将用户名及密码以BASE64加密,加密后的密文将附加于请求信息中, 如当用户名为anjuta,密码为:123456时,客户端将用

  • 浅谈数据库缓存最终一致性的四种方案

    浅谈数据库缓存最终一致性的四种方案

    背景 缓存是软件开发中一个非常有用的概念,数据库缓存更是在项目中必然会遇到的场景.而缓存一致性的保证,更是在面试中被反复问到,这里进行一下总结,针对不同的要求,选择恰到好处的一致性方案. 缓存是什么 存储的速度是有区别的.缓存就是把低速存储的结果,临时保存在高速存储的技术. 如图所示,金字塔更上面的存储,可以作为下面存储的缓存. 我们本次的讨论,主要针对数据库缓存场景,将以redis作为mysql的缓存为案例来进行. 为什么需要缓存 存储如mysql通常支持完整的ACID特性,因为可靠性,持久性

  • 浅谈Android中AsyncTask的工作原理

    概述 实际上,AsyncTask内部是封装了Thread和Handler.虽然AsyncTask很方便的执行后台任务,以及在主线程上更新UI,但是,AsyncTask并不合适进行特别耗时的后台操作,对于特别耗时的任务,个人还是建议使用线程池.好了,话不多说了,我们先看看AsyncTask的简单用法吧. AsyncTask使用方法 AsyncTask是一个抽象的泛型类.简单的介绍一下它的使用方式代码如下: package com.example.huangjialin.myapplication;

  • 浅谈数据库事务四大特性

    数据库四大特性分别是:原子性.一致性.分离性.持久性.下面我们看看具体介绍. 原子性 事务的原子性指的是,事务中包含的程序作为数据库的逻辑工作单位,它所做的对数据修改操作要么全部执行,要么完全不执行.这种特性称为原子性. 事务的原子性要求,如果把一个事务可看作是一个程序,它要么完整的被执行,要么完全不执行.就是说事务的操纵序列或者完全应用到数据库或者完全不影响数据库.这种特性称为原子性. 假如用户在一个事务内完成了对数据库的更新,这时所有的更新对外部世界必须是可见的,或者完全没有更新.前者称事务

  • 浅谈javascript中new操作符的原理

    浅谈javascript中new操作符的原理

    javascript中的new是一个语法糖,对于学过c++,java 和c#等面向对象语言的人来说,以为js里面是有类和对象的区别的,实现上js并没有类,一切皆对象,比java还来的彻底 new的过程实际上是创建一个新对象,把新象的原型设置为构造器函数的原型,在使用new的过程中,一共有3个对象参与了协作,构造器函数是第一个对象,原型对象是二个,新生成了一个空对象是第三个对象,最终返回的是一个空对象,但这个空对象不是真空的,而是已经含有原型的引用(__proto__) 步骤如下: (1) 创建一

  • 浅谈web上存漏洞及原理分析、防范方法（文件名检测漏洞）

    我们通过前篇:<浅谈web上存漏洞及原理分析.防范方法(安全文件上存方法)>,已经知道后端获取服务器变量,很多来自客户端传入的.跟普通的get,post没有什么不同.下面我们看看,常见出现漏洞代码.1.检测文件类型,并且用用户上存文件名保存 复制代码 代码如下: if(isset($_FILES['img'])){    $file = save_file($_FILES['img']); if($file===false) exit('上存失败!'); echo "上存成功!&qu

  • 浅谈Jave枚举的作用与好处

    枚举是一种规范它规范了参数的形式,这样就可以不用考虑类型的不匹配并且显式的替代了int型参数可能带来的模糊概念 枚举像一个类,又像一个数组. Enum作为Sun全新引进的一个关键字,看起来很象是特殊的class, 它也可以有自己的变量,可以定义自己的方法,可以实现一个或者多个接口. 当我们在声明一个enum类型时,我们应该注意到enum类型有如下的一些特征. 1．它不能有public的构造函数,这样做可以保证客户代码没有办法新建一个enum的实例. 2．所有枚举值都是public , stati

随机推荐