索引_索引卡 - CSDN
索引 订阅
在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录,可以根据目录中的页码快速找到所需的内容。索引提供指向存储在表的指定列中的数据值的指针,然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值,然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快,可快速访问数据库表中的特定信息。当表中有大量记录时,若要对表进行查询,第一种搜索信息方式是全表搜索,是将所有记录一一取出,和查询条件进行一一对比,然后返回满足条件的记录,这样做会消耗大量数据库系统时间,并造成大量磁盘I/O操作;第二种就是在表中建立索引,然后在索引中找到符合查询条件的索引值,最后通过保存在索引中的ROWID(相当于页码)快速找到表中对应的记录。 展开全文
在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录,可以根据目录中的页码快速找到所需的内容。索引提供指向存储在表的指定列中的数据值的指针,然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值,然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快,可快速访问数据库表中的特定信息。当表中有大量记录时,若要对表进行查询,第一种搜索信息方式是全表搜索,是将所有记录一一取出,和查询条件进行一一对比,然后返回满足条件的记录,这样做会消耗大量数据库系统时间,并造成大量磁盘I/O操作;第二种就是在表中建立索引,然后在索引中找到符合查询条件的索引值,最后通过保存在索引中的ROWID(相当于页码)快速找到表中对应的记录。
信息
中文名
索引
外文名
index
作    用
应于表的SQL语句执行得更快
分    类
数据库概念
索引发展历史
旧称通检、备检或引得。组成的基本单位是索引款目。款目一般包括索引词、说明或注释语 、出处3项内容 。所有索引款目实现有序化编排。其本质特征是只揭示内容出处或文献线索 ,并不直接提供事实、资料本身。主要功能是为人们准确、迅速地获得文献资料提供线索性指引。常见的索引主要有报刊论文资料索引、文集篇目索引、语词索引、文句索引、关键词索引、专名索引、主题索引等。索引最早出现于西方,主要是中世纪欧洲宗教著作的索引。18世纪以后西方开始有主题索引,至19世纪末,内容分析索引被广泛使用。中国的索引出现较晚。一般认为,明末傅山所编的《两汉书姓名韵》是现存最早的人名索引。清代乾嘉时期,章学诚曾力倡编纂群书综合索引。20世纪20年代,随着西方索引理论与编制技术的传入,中国现代意义上的索引编制与研究才蓬勃展开 。1930年钱亚新发表《索引和索引法》,1932年洪业发表《引得说》,标志着具有中国特色的现代索引理论、技术已迅速发展起来。20世纪50年代,计算机技术被运用于索引编制 。此后,机编索引的大量出现,使索引编制理论、技术、索引载体形式发生了深刻变革。SQL标准中没有涉及索引,但商用关系数据库管理系统一般都支持索引机制,只是不同的关系数据库管理系统支持的索引类型不尽相同。索引已经成为关系数据库非常重要的部分。它们被用作包含所关心数据的表指针。通过一个索引,能从表中直接找到一个特定的记录,而不必连续顺序扫描这个表,一次一个地去查找。对于大的表,索引是必要的。没有索引,要想得到一个结果要等好几个小时、好几天,而不是几秒钟。 [1] 
收起全文
  • 索引

    2019-07-10 23:29:19
    1、索引是什么  索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。 可以理解为“排好序的快速查找数据结构” 在数据之外,数据库系统还维护着满足特定查找算法的数据结构...

    1、索引是什么

      索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。
      可以理解为“排好序的快速查找数据结构”
      在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,
    这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。
    MySQL索引的建立对于MySQL的高效运行是很重要的,索引可以大大提高MySQL的检索速度。
    打个比方,如果合理的设计且使用索引的MySQL是一辆兰博基尼的话,那么没有设计和使用索引的MySQL就是一个人力三轮车。
    创建索引时,你需要确保该索引是应用在 SQL 查询语句的条件(一般作为 WHERE 子句的条件)。

    2、优势

      类似大学图书馆建书目索引,提高数据检索效率,降低数据库的IO成本。
      通过索引对数据进行排序,降低数据排序的成本,降低了CPU的消耗。

    3、劣势

      实际上索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录,所以索引列也是要占空间的。
      虽然索引大大提高了查询速度,同时确会降低更新表的速度,如对表进行INSERT、UPDATE、DELETE。
      因为更新表时,MySQL不仅要保存数据,还要保存一下索引文件每次更新添加了索引列的字段。
    都会调整因为更新所带来的键值变化后的索引信息。 
    建立索引会占用磁盘空间的索引文件。

    4、索引的分类

      主键索引、唯一索引、普通索引、全文索引、组合索引

    5、基本语法

    1,INDEX(普通索引):

    ALTER TABLE 'table_name' ADD INDEX index_name('col')

    最基本的索引,没有任何限制

    2,UNIQUE(唯一索引):

    ALTER TABLE 'table_name' ADD UNIQUE('col')

    与“普通索引”类似,不同的就是:索引列的值必须唯一,但允许有空值。

    3,PRIMARY KEY(主键索引):

    ALTER TABLE 'table_name' ADD PRIMARY KEY('col')

    是一种特殊的唯一索引,不允许有空值。
    4,FULLTEXT(全文索引):

    ALTER TABLE 'table_name' ADD FULLTEXT('col')

    仅可用于MyISAM和InoDB,针对较大的数据,生成全文索引很耗时耗空间
    5,组合索引:

    ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')

    为了更多的提高mysql效率可建立组合索引,遵循“最左前缀”原则。创建复合索引应该将最常用(频率)做限制条件的列放在最左边,一次递减。组合索引最左字段用in是可以用到索引的。相当于建立了col1,col1col2,col1col2col3三个索引
    修改索引名称(mysql)
    对于MySQL 5.7及以上版本,可以执行以下命令:

    ALTER TABLE tbl_name RENAME INDEX old_index_name TO new_index_name

    对于MySQL 5.7以前的版本,可以执行下面两个命令:

    ALTER TABLE tbl_name DROP INDEX old_index_name

    ALTER TABLE tbl_name ADD INDEX new_index_name(column_name)

        
    6、哪些情况需要创建索引
        ①主键自动建立唯一索引
        ②频繁作为查询条件的字段应该创建索引
        ③查询中与其他表关联的字段,外键关系建立索引
        ④频繁更新的字段不适合建立索引,因为每次更新不单单是更新了记录还会更新索引
        ⑤WHERE条件里用不到的字段不创建索引
        ⑥单键/组合索引的选择问题,who?(在高并发下倾向创建组合索引)
        ⑦查询中排序的字段,排序的字段若通过索引去访问将大大提高排序速度
        ⑧查询中统计或者分组字段
    7、哪些情况不要创建索引
      ①表记录太少
      ②经常增删改的表
        提高了查询速度,同时却会降低更新表的速度,如对表进行INSERT、UPDATE、和DELETE。
        因为更新表时,MySQL不仅要保存数据,还要保存一下索引文件。
        数据重复且分布平均的表字段,因此应该只为最经常查询和最经常排序的数据建立索引。
      ③注意,如果某个数据列包含许多重复的内容,为它建立索引就没有太大的实际效果。

    索引使用注意事项

    1,不要滥用索引

    ①,索引提高查询速度,却会降低更新表的速度,因为更新表时,mysql不仅要更新数据,保存数据,还要更新索引,保存索引
    ②,索引会占用磁盘空间

    2,索引不会包含含有NULL值的列

    复合索引只要有一列含有NULL值,那么这一列对于此符合索引就是无效的,因此我们在设计数据库设计时不要让字段的默认值为NULL。

    3,MySQL查询只是用一个索引

    如果where字句中使用了索引的话,那么order by中的列是不会使用索引的

    4,like

    like '%aaa%'不会使用索引而like "aaa%"可以使用索引

    转载于:https://www.cnblogs.com/BrokenHeart/p/10616159.html

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

    2017-09-17 21:48:37
    这篇文章是介绍MySQL数据库中的索引是如何根据需求一步步演变最终成为B+树结构的以及针对B+树索引的查询,插入,删除,更新等操作的处理方法。Oracle和DB2数据库索引的实现基本上也是大同小异的。文章写得很通俗易懂...

    这篇文章是介绍MySQL数据库中的索引是如何根据需求一步步演变最终成为B+树结构的以及针对B+树索引的查询,插入,删除,更新等操作的处理方法。Oracle和DB2数据库索引的实现基本上也是大同小异的。文章写得很通俗易懂,就转在这了。关于B+树和索引内部结构可以参考:《B 树、B- 树、B+ 树和B* 树》和《深入理解DB2索引(Index)》。


    00 – 背景知识

    - B-Tree & B+Tree

      http://en.wikipedia.org/wiki/B%2B_tree
      http://en.wikipedia.org/wiki/B-tree

    - 折半查找(Binary Search)

      http://en.wikipedia.org/wiki/Binary_search_algorithm

    - 数据库的性能问题

      A. 磁盘IO性能非常低,严重的影响数据库系统的性能。
      B. 磁盘顺序读写比随机读写的性能高很多。

    - 数据的基本存储结构

      A. 磁盘空间被划分为许多大小相同的块(Block)或者页(Page).
      B. 一个表的这些数据块以链表的方式串联在一起。
      C. 数据是以行(Row)为单位一行一行的存放在磁盘上的块中,如图所示.
      D. 在访问数据时,一次从磁盘中读出或者写入至少一个完整的Block。

                                                  Fig. 1


    01 – 数据基本操作的实现

      基本操作包括:INSERT、UPDATE、DELETE、SELECT。

    - SELECT

      A. 定位数据
      B. 读出数据所在的块,对数据加工
      C. 返回数据给用户

    - UPDATE、DELETE

      A. 定位数据
      B. 读出数据所在的块,修改数据
      C. 写回磁盘

    - INSERT

      A. 定位数据要插入的页(如果数据需要排序)
      B. 读出要插入的数据页,插入数据.
      C. 写回磁盘

    如何定位数据?
    - 表扫描(Table Scan)

      A. 从磁盘中依次读出所有的数据块,一行一行的进行数据匹配。
      B. 时间复杂度 是O(n), 如果所有的数据占用了100个块。尽管只查询一行数据,
         也需要读出所有100个块的数据。
      C. 需要大量的磁盘IO操作,极大的影响了数据定位的性能。

    因为数据定位操作是所有数据操作必须的操作,数据定位操作的效率会直接影响所有的数据操作的效率。
    因此我们开始思考,如何来减少磁盘的IO?
    - 减少磁盘IO

      A. 减少数据占用的磁盘空间
         压缩算法、优化数据存储结构
      B. 减少访问数据的总量
         读出或写入的数据中,有一部分是数据操作所必须的,这部分称作有效数据。剩余的
         部分则不是数据操作必须的数据,称为无效数据。例如,查询姓名是‘张三’的记录。
         那么这条记录是有效记录,其他记录则是无效记录。我们要努力减少无效数据的访问。

    02 – 索引的产生

    - 键(Key)

      首先,我们发现在多数情况下,定位操作并不需要匹配整行数据。而是很规律的只匹配某一个
      或几个列的值。 例如,图中第1列就可以用来确定一条记录。这些用来确定一条数据的列,统 
      称为键(Key).

                        Fig. 2

    - Dense Index

      根据减少无效数据访问的原则,我们将键的值拿过来存放到独立的块中。并且为每一个键值添
      加一个指针, 指向原来的数据块。如图所示,


                                Fig. 3

      这就是‘索引’的祖先Dense Index. 当进行定位操作时,不再进行表扫描。而是进行
      索引扫描(Index Scan),依次读出所有的索引块,进行键值的匹配。当找到匹配的键值后,
      根据该行的指针直接读取对应的数据块,进行操作。假设一个块中能存储100行数据,
      10,000,000行的数据需要100,000个块的存储空间。假设键值列(+指针)占用一行数据
      1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储
      空间换来了大约全表扫描10倍的定位效率。

    03 – 索引的进化

      在实际的应用中,这样的定位效率仍然不能满足需求。很多人可能已经想到了,通过排序和查找
      算法来减少IO的访问。因此我们开始尝试对Dense Index进行排序存储,并且期望利用排序查
      找算法来减少磁盘IO。

    - 折半块查找

      A. 对Dense Index排序
      B. 需要一个数组按顺序存储索引块地址。以块为单位,不存储所有的行的地址。
      C. 这个索引块地址数组,也要存储到磁盘上。将其单独存放在一个块链中,如下图所示。
      D. 折半查找的时间复杂度是O(log 2(N))。在上面的列子中,dense索引总共有10,000个块。假设1个块
         能存储2000个指针,需要5个块来存储这个数组。通过折半块查找,我们最多只需要读取
         5(数组块)+ 14(索引块log 2(10000))+1(数据块)=20个块。


                                                                    Fig. 4

     - Sparse Index

      实现基于块的折半查找时发现,读出每个块后只需要和第一行的键值匹配,就可以决定下一个块
      的位置(方向)。 因此有效数据是每个块(最后一个块除外)的第一行的数据。还是根据减少无
      效数据IO的原则,将每一个块的第一行的数据单独拿出来,和索引数组的地址放到一起。这样就
      可以直接在这个数组上进行折半查找了。如下图所示,这个数组就进化成了Sparse Index


                                                            Fig. 5

      因为Sparse Index和Dense Index的存储结构是相同的,所以占用的空间也相同。大约需
      要10个块来存储10000个Dense Index块的地址和首行键值。通过Sparse索引,仅需要读
      取10(Sparse块)+1(Dense块)+1(数据块)=12个块.

    - 多层Sparse Index

      因为Sparse Index本身是有序的,所以可以为Sparse Index再建sparse Index。通过
      这个方法,一层一层的建立 Sparse Indexes,直到最上层的Sparse Index只占用一个块
      为止,如下图所示.


                                           Fig. 6

      A. 这个最上层的Sparse Index称作整个索引树的根(root).
      B. 每次进行定位操作时,都从根开始查找。
      C. 每层索引只需要读出一个块。
      D. 最底层的Dense Index或数据称作叶子(leaf).
      E. 每次查找都必须要搜索到叶子节点,才能定位到数据。
      F. 索引的层数称作索引树的高度(height).
      G. 索引的IO性能和索引树的高度密切相关。索引树越高,磁盘IO越多。

      在我们的例子中的Sparse Index,只有10个块,因此我们只需要再建立一个Sparse Index.
      通过两层Sparse Index和一层Dense Index查找时,只需读取1+1+1+1=4个块。

    - Dense Index和Sparse Index的区别

      A. Dense Index包含所有数据的键值,但是Sparse Index仅包含部分键值。
         Sparse Index占用更少的磁盘空间。
      B. Dense Index指向的数据可以是无序的,但是Sparse Index的数据必须是有序的。
      C. Sparse Index 可以用来做索引的索引,但是Dense Index不可以。
      D. 在数据是有序的时候,Sparse Index更有效。因此Dense Index仅用于无序的数据。
      E. 索引扫描(Index Scan)实际上是对Dense Index层进行遍历。

    - 簇索引(Clustered Index)和辅助索引(Secondary Index)

      如果数据本身是基于某个Key来排序的,那么可以直接在数据上建立sparse索引,
      而不需要建立一个dense索引层(可以认为数据就是dense索引层)。 如下图所示:


                                                    Fig. 7

      这个索引就是我们常说的“Clustered Index”,而用来排序数据的键叫做主键Primary Key.

      A. 一个表只能有一个Clustered Index,因为数据只能根据一个键排序.
      B. 用其他的键来建立索引树时,必须要先建立一个dense索引层,在dense索引层上对此键的值
         进行排序。这样的索引树称作Secondary Index.
      C. 一个表上可以有多个Secondary Index.
      D. 对簇索引进行遍历,实际上就是对数据进行遍历。因此簇索引的遍历效率比辅组索引低。
         如SELECT count(*) 操作,使用辅组索引遍历的效率更高。

    - 范围搜索(Range Search)

      由于键值是有序的,因此可以进行范围查找。只需要将数据块、Dense Index块分别以双向链表
      的方式进行连接, 就可以实现高效的范围查找。如下图所示:


                                                    Fig. 8   范围查找的过程:   A. 选择一个合适的边界值,定位该值数据所在的块   B. 然后选择合适的方向,在数据块(或Dense Index块)链中进行遍历。   C. 直到数据不满足另一个边界值,结束范围查找。 是不是看着这个索引树很眼熟?换个角度看看这个图吧!


        Fig. 9

    这分明就是传说中的B+Tree.
    - 索引上的操作
      A. 插入键值
      B. 删除键值
      C. 分裂一个节点
      D. 合并两个节点
    这些操作在教科书上都有介绍,这里就不介绍了。
    先写到这吧,实在写不动了,想明白容易,写明白就难了。下一篇里,打算谈谈标准B+Tree的几个问题,以及在
    实现过程中,B+Tree的一些变形。

    教科书上的B+Tree是一个简化了的,方便于研究和教学的B+Tree。然而在数据库实现时,为了
    更好的性能或者降低实现的难度,都会在细节上进行一定的变化。下面以InnoDB为例,来说说
    这些变化。

    04 - Sparse Index中的数据指针

      在“由浅入深理解索引的实现(1)”中提到,Sparse Index中的每个键值都有一个指针指向
      所在的数据页。这样每个B+Tree都有指针指向数据页。如图Fig.10所示:


    Fig.10

      如果数据页进行了拆分或合并操作,那么所有的B+Tree都需要修改相应的页指针。特别是
      Secondary B+Tree(辅助索引对应的B+Tree), 要对很多个不连续的页进行修改。同时也需要对
      这些页加锁,这会降低并发性。

      为了降低难度和增加更新(分裂和合并B+Tree节点)的性能,InnoDB 将 Secondary B+Tree中
      的指针替换成了主键的键值。如图Fig.11所示:


    Fig.11

      这样就去除了Secondary B+Tree对数据页的依赖,而数据就变成了Clustered B+Tree(簇
      索引对应的B+Tree)独占的了。对数据页的拆分及合并操作,仅影响Clustered B+Tree. 因此
      InnoDB的数据文件中存储的实际上就是多个孤立B+Tree。

      一个有趣的问题,当用户显式的把主键定义到了二级索引中时,还需要额外的主键来做二级索引的
      数据吗(即存储2份主键)? 很显然是不需要的。InnoDB在创建二级索引的时候,会判断主键的字段
      是否已经被包含在了要创建的索引中。

      接下来看一下数据操作在B+Tree上的基本实现。

    - 用主键查询

      直接在Clustered B+Tree上查询。

    - 用辅助索引查询
      A. 在Secondary B+Tree上查询到主键。
      B. 用主键在Clustered B+Tree

    可以看出,在使用主键值替换页指针后,辅助索引的查询效率降低了。
      A. 尽量使用主键来查询数据(索引遍历操作除外).
      B. 可以通过缓存来弥补性能,因此所有的键列,都应该尽量的小。

    - INSERT
      A. 在Clustered B+Tree上插入数据
      B. 在所有其他Secondary B+Tree上插入主键。

    - DELETE
      A. 在Clustered B+Tree上删除数据。
      B. 在所有其他Secondary B+Tree上删除主键。

    - UPDATE 非键列
      A. 在Clustered B+Tree上更新数据。

    - UPDATE 主键列
      A. 在Clustered B+Tree删除原有的记录(只是标记为DELETED,并不真正删除)。
      B. 在Clustered B+Tree插入新的记录。
      C. 在每一个Secondary B+Tree上删除原有的数据。(有疑问,看下一节。)
      D. 在每一个Secondary B+Tree上插入原有的数据。

    - UPDATE 辅助索引的键值
      A. 在Clustered B+Tree上更新数据。
      B. 在每一个Secondary B+Tree上删除原有的主键。
      C. 在每一个Secondary B+Tree上插入原有的主键。

    更新键列时,需要更新多个页,效率比较低。
      A. 尽量不用对主键列进行UPDATE操作。
      B. 更新很多时,尽量少建索引。

    05 – 非唯一键索引

      教科书上的B+Tree操作,通常都假设”键值是唯一的“。但是在实际的应用中Secondary Index是允
      许键值重复的。在极端的情况下,所有的键值都一样,该如何来处理呢?
      InnoDB 的 Secondary B+Tree中,主键也是此键的一部分。
      Secondary Key = 用户定义的KEY + 主键。如图Fig.12所示:


    Fig.12

      注意主键不仅做为数据出现在叶子节点,同时也作为键的一部分出现非叶子节点。对于非唯一键来说,
      因为主键是唯一的,Secondary Key也是唯一的。当然,在插入数据时,还是会根据用户定义的Key,
      来判断唯一性。按理说,如果辅助索引是唯一的(并且所有字段不能为空),就不需要这样做。可是,
      InnoDB对所有的Secondary B+Tree都这样创建。

    还没弄明白有什么特殊的用途?有知道的朋友可以帮忙解答一下。
    也许是为了降低代码的复杂性,这是我想到的唯一理由。

    弄清楚了,即便是非空唯一键,在二级索引的B+Tree中也可能重复,因此必须要将主键加入到非叶子节点。

    06 – <Key, Pointer>对

      标准的B+Tree的每个节点有K个键值和K+1个指针,指向K+1个子节点。如图Fig.13:


    Fig.13(图片来自于WikiPedia)

      而在“由浅入深理解索引的实现(1)”中Fig.9的B+Tree上,每个节点有K个键值和K个指针。
      InnoDB的B+Tree也是如此。如图Fig.14所示:


    Fig.14

      这样做的好处在于,键值和指针一一对应。我们可以将一个<Key,Pointer>对看作一条记录。
      这样就可以用数据块的存储格式来存储索引块。因为不需要为索引块定义单独的存储格式,就
      降低了实现的难度。

    - 插入最小值

      当考虑在变形后的B+Tree上进行INSERT操作时,发现了一个有趣的问题。如果插入的数据的健
      值比B+Tree的最小键值小时,就无法定位到一个适当的数据块上去(<Key,Pointer>中的Key
      代表了子节点上的键值是>=Key的)。例如,在Fig.5的B+Tree中插入键值为0的数据时,无法
      定位到任何节点。

      在标准的B+Tree上,这样的键值会被定位到最左侧的节点上去。这个做法,对于Fig.5中的
      B+Tree也是合理的。Innodb的做法是,将每一层(叶子层除外)的最左侧节点的第一条记录标
      记为最小记录(MIN_REC).在进行定位操作时,任何键值都比标记为MIN_REC的键值大。因此0
      会被插入到最左侧的记录节点上。如Fig.15所示:


                                                   Fig.15

    07 – 顺序插入数据

      Fig.16是B-Tree的插入和分裂过程,我们看看有没有什么问题?


    Fig.16(图片来自于WikiPedia)

      标准的B-Tree分裂时,将一半的键值和数据移动到新的节点上去。原有节点和新节点都保留一半
      的空间,用于以后的插入操作。当按照键值的顺序插入数据时,左侧的节点不可能再有新的数据插入。
      因此,会浪费约一半的存储空间。

      解决这个问题的基本思路是:分裂顺序插入的B-Tree时,将原有的数据都保留在原有的节点上。
      创建一个新的节点,用来存储新的数据。顺序插入时的分裂过程如Fig.17所示:


    Fig.17

      以上是以B-Tree为例,B+Tree的分裂过程类似。InnoDB的实现以这个思路为基础,不过要复杂
      一些。因为顺序插入是有方向性的,可能是从小到大,也可能是从大到小的插入数据。所以要区
      分不同的情况。如果要了解细节,可参考以下函数的代码。
        btr_page_split_and_insert();
        btr_page_get_split_rec_to_right();
        btr_page_get_split_rec_to_right();

    InnoDB的代码太复杂了,有时候也不敢肯定自己的理解是对的。因此写了一个小脚本,来打印InnoDB数
    据文件中B+Tree。这样可以直观的来观察B+Tree的结构,验证自己的理解是否正确。

    很多知识来自于下面这两本书。 “Database Systems: The Complete Book (2nd Edition) ”

    “Transaction Processing: Concepts and Techniques”


    转载自:http://www.mysqlops.com/2011/11/24/understanding_index.html

    展开全文
  • 索引的数据结构分析,数据库面试到索引最常见的问题分析,我总结了一下。

    点赞再看,养成习惯,微信搜索【三太子敖丙】我所有文章都在这里,本文 GitHub https://github.com/JavaFamily 已收录,有一线大厂面试完整考点,文末有福利

    前言

    写数据库,我第一时间就想到了MySQL、Oracle、索引、存储过程、查询优化等等。

    不知道大家是不是跟我想得一样,我最想写的是索引,为啥呢?

    以下这个面试场景,不知道大家熟悉不熟悉:

    面试官:数据库有几千万的数据,查询又很慢我们怎么办?

    面试者:加索引。

    面试官:那索引有哪些数据类型?索引是怎么样的一种结构?哪些字段又适合索引呢?B+的优点?聚合索引和非聚合索引的区别?为什么说索引会降低插入、删除、修改等维护任务的速度?……..

    面试者:面试官怎么出我们公司门来着😂。

    是的大家可能都知道慢了加索引,那为啥加,在什么字段上加,以及索引的数据结构特点,优点啥的都比较模糊或者甚至不知道。

    那我们也不多BB了,直接开始这次的面试吧。

    正文

    我看你简历上写到了熟悉MySQL数据库以及索引的相关知识,我们就从索引开始,索引有哪些数据结构?

    Hash、B+

    大家去设计索引的时候,会发现索引类型是可以选择的。

    为什么哈希表、完全平衡二叉树、B树、B+树都可以优化查询,为何Mysql独独喜欢B+树?

    我先聊一下Hash:

    大家可以先看一下下面的动图

    注意字段值所对应的数组下标是哈希算法随机算出来的,所以可能出现哈希冲突

    那么对于这样一个索引结构,现在来执行下面的sql语句:

    select * from sanguo where name='鸡蛋'

    可以直接对‘鸡蛋’按哈希算法算出来一个数组下标,然后可以直接从数据中取出数据并拿到所对应那一行数据的地址,进而查询那一行数据, 那么如果现在执行下面的sql语句:

    select * from sanguo where name>'鸡蛋'

    则无能为力,因为哈希表的特点就是可以快速的精确查询,但是不支持范围查询

    如果做成了索引,那速度也是很慢的,要全部扫描。

    问个题外话,那Hash表在哪些场景比较适合?

    等值查询的场景,就只有KV(Key,Value)的情况,例如Redis、Memcached等这些NoSQL的中间件。

    你说的是无序的Hash表,那有没有有序的数据结构?

    有序数组,它就比较优秀了呀,它在等值查询的和范围查询的时候都很Nice。

    那它完全没有缺点么?

    不是的,有序的适合静态数据,因为如果我们新增、删除、修改数据的时候就会改变他的结构。

    比如你新增一个,那在你新增的位置后面所有的节点都会后移,成本很高。

    那照你这么说他根本就不优秀啊,特点也没地方放。

    此言差矣,可以用来做静态存储引擎啊,用来保存静态数据,例如你2019年的支付宝账单,2019年的淘宝购物记录等等都是很合适的,都是不会变动的历史数据。

    有点东西啊小伙子,那二叉树呢?

    二叉树的新增和结构如图:

    二叉树的结构我就不在这里多BB了,不了解的朋友可以去看看数据结构章节。

    二叉树是有序的,所以是支持范围查询的。

    但是他的时间复杂度是O(log(N)),为了维持这个时间复杂度,更新的时间复杂度也得是O(log(N)),那就得保持这棵树是完全平衡二叉树了。

    怎么听你一说,平衡二叉树用来做索引还不错呢?

    此言差矣,索引也不只是在内存里面存储的,还是要落盘持久化的,可以看到图中才这么一点数据,如果数据多了,树高会很高,查询的成本就会随着树高的增加而增加。

    为了节约成本很多公司的磁盘还是采用的机械硬盘,这样一次千万级别的查询差不多就要10秒了,这谁顶得住啊?

    如果用B树呢?

    同理来看看B树的结构:

    可以发现同样的元素,B树的表示要比完全平衡二叉树要“矮”,原因在于B树中的一个节点可以存储多个元素。

    B树其实就已经是一个不错的数据结构,用来做索引效果还是不错的。

    那为啥没用B树,而用了B+树?

    一样先看一下B加的结构:

    我们可以发现同样的元素,B+树的表示要比B树要“胖”,原因在于B+树中的非叶子节点会冗余一份在叶子节点中,并且叶子节点之间用指针相连。

    那么B+树到底有什么优势呢?

    其实很简单,我们看一下上面的数据结构,最开始的Hash不支持范围查询,二叉树树高很高,只有B树跟B+有的一比。

    B树一个节点可以存储多个元素,相对于完全平衡二叉树整体的树高降低了,磁盘IO效率提高了。

    而B+树是B树的升级版,只是把非叶子节点冗余一下,这么做的好处是为了提高范围查找的效率

    提高了的原因也无非是会有指针指向下一个节点的叶子节点。

    小结:到这里可以总结出来,Mysql选用B+树这种数据结构作为索引,可以提高查询索引时的磁盘IO效率,并且可以提高范围查询的效率,并且B+树里的元素也是有序的。

    那么,一个B+树的节点中到底存多少个元素最合适你有了解过么?

    额这个这个?卧*有点懵逼呀。

    过了一会还是没想出,只能老实交代:这个不是很了解咳咳。

    你可以换个角度来思考B+树中一个节点到底多大合适?

    B+树中一个节点为一页或页的倍数最为合适

    为啥?

    因为如果一个节点的大小小于1页,那么读取这个节点的时候其实也会读出1页,造成资源的浪费。

    如果一个节点的大小大于1页,比如1.2页,那么读取这个节点的时候会读出2页,也会造成资源的浪费。

    所以为了不造成浪费,所以最后把一个节点的大小控制在1页、2页、3页、4页等倍数页大小最为合适。

    你提到了页的概念,能跟我简单说一下么?

    首先Mysql的基本存储结构是(记录都存在页里边):

    • 各个数据页可以组成一个双向链表

    • 每个数据页中的记录又可以组成一个单向链表

    • - 每个数据页都会为存储在它里边儿的记录生成一个页目录,在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录

    • 其他列(非主键)作为搜索条件:只能从最小记录开始依次遍历单链表中的每条记录

    所以说,如果我们写 select * from user where username='丙丙'这样没有进行任何优化的sql语句,默认会这样做:

    • 定位到记录所在的页

    • - 需要遍历双向链表,找到所在的页

    • 从所在的页内中查找相应的记录

    • - 由于不是根据主键查询,只能遍历所在页的单链表了

    很明显,在数据量很大的情况下这样查找会很慢!看起来跟回表有点点像。

    哦?回表你聊一下。

    卧槽,该死,我嘴干嘛。

    回表大概就是我们有个主键为ID的索引,和一个普通name字段的索引,我们在普通字段上搜索:

    select * from table where name = '丙丙'

    执行的流程是先查询到name索引上的“丙丙”,然后找到他的id是2,最后去主键索引,找到id为2对应的值。

    回到主键索引树搜索的过程,就是回表。不过也有方法避免回表,那就是覆盖索引

    哦?那你再跟我聊一下覆盖索引呗?

    !!! 我这个嘴。。。

    这个其实比较好理解,刚才我们是 select * ,查询所有的,我们如果只查询ID那,其实在Name字段的索引上就已经有了,那就不需要回表了。

    覆盖索引可以减少树的搜索次数,提升性能,他也是我们在实际开发过程中经常用来优化查询效率的手段。

    很多联合索引的建立,就是为了支持覆盖索引,特定的业务能极大的提升效率。

    索引的最左匹配原则知道么?

    最左匹配原则

    • 索引可以简单如一个列 (a),也可以复杂如多个列 (a,b,c,d),即联合索引
    • 如果是联合索引,那么key也由多个列组成,同时,索引只能用于查找key是否存在(相等),遇到范围查询 (>、<、between、like左匹配)等就不能进一步匹配了,后续退化为线性查找。
    • 因此,列的排列顺序决定了可命中索引的列数

    例子:

    • 如有索引 (a,b,c,d),查询条件 a=1 and b=2 and c>3 and d=4,则会在每个节点依次命中a、b、c,无法命中d。(c已经是范围查询了,d肯定是排不了序了)

    总结

    索引在数据库中是一个非常重要的知识点!

    上面谈的其实就是索引最基本的东西,N叉树,跳表、LSM我都没讲,同时要创建出好的索引要顾及到很多的方面:

    • 最左前缀匹配原则。这是非常重要、非常重要、非常重要(重要的事情说三遍)的原则,MySQL会一直向右匹配直到遇到范围查询 (>,<,BETWEEN,LIKE)就停止匹配。
    • 尽量选择区分度高的列作为索引,区分度的公式是 COUNT(DISTINCT col)/COUNT(*)。表示字段不重复的比率,比率越大我们扫描的记录数就越少。
    • 索引列不能参与计算,尽量保持列“干净”。比如, FROM_UNIXTIME(create_time)='2016-06-06' 就不能使用索引,原因很简单,B+树中存储的都是数据表中的字段值,但是进行检索时,需要把所有元素都应用函数才能比较,显然这样的代价太大。所以语句要写成 : create_time=UNIX_TIMESTAMP('2016-06-06')。
    • 尽可能的扩展索引,不要新建立索引。比如表中已经有了a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可。
    • 单个多列组合索引和多个单列索引的检索查询效果不同,因为在执行SQL时,MySQL只能使用一个索引,会从多个单列索引中选择一个限制最为严格的索引(经指正,在MySQL5.0以后的版本中,有“合并索引”的策略,翻看了《高性能MySQL 第三版》,书作者认为:还是应该建立起比较好的索引,而不应该依赖于“合并索引”这么一个策略)。
    • “合并索引”策略简单来讲,就是使用多个单列索引,然后将这些结果用“union或者and”来合并起来

    思路文献参考:

    《MySQL实战》

    《高性能MySQL》

    最后部分内容来自->java3y《索引和锁》

    丁奇《MySQL实战》

    絮叨

    之前在B站传了第一个视频:

    大家反馈效果还是ok的,我后续会多多尝试的,也希望把改进的建议留言反馈给我。

    我去年拍摄了第一个超级粗糙的vlog:

    因为拍摄剪辑手法都很垃圾,我就删了,但是最近又想着放上去,在纠结哈哈,想看留个言我就传了哈哈,我们下期间。

    今天丙丙也开始了来杭16天后的第一次上班,很开心我们公司在杭州第一批复工的名单中,我已经16天没和人这样说过话了,太开心了,不过不能开空调还得开窗户通风,真的是超级超级冷。

    这熟悉的工位,这熟悉的显示器,我的眼角又……

    Tip:本来有很多我准备的资料的,但是都是外链,或者不合适的分享方式,博客的运营小姐姐提醒了我,所以大家去公众号回复【资料】好了。

    白嫖不好,创作不易,各位的点赞就是丙丙创作的最大动力,我们下篇文章见!

    持续更新,未完待续……


    絮叨

    另外,敖丙把自己的面试文章整理成了一本电子书,共 1630页!目录如下

    现在免费送给大家,在我的公众号三太子敖丙回复 【888】 即可获取。

    我是敖丙,一个在互联网苟且偷生的程序员。

    你知道的越多,你不知道的越多人才们的 【三连】 就是丙丙创作的最大动力,我们下期见!

    注:如果本篇博客有任何错误和建议,欢迎人才们留言!


    文章持续更新,可以微信搜索「 三太子敖丙 」第一时间阅读,回复【资料】有我准备的一线大厂面试资料和简历模板,本文 GitHub https://github.com/JavaFamily 已经收录,有大厂面试完整考点,欢迎Star。

    展开全文
  • 说到索引,很多人都知道“索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址,在数据十分庞大的时候,索引可以大大加快查询的速度,这是因为使用索引后可以不用扫描全表来定位某...

    说到索引,很多人都知道“索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址,在数据十分庞大的时候,索引可以大大加快查询的速度,这是因为使用索引后可以不用扫描全表来定位某行的数据,而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。

    但是索引是怎么实现的呢?因为索引并不是关系模型的组成部分,因此不同的DBMS有不同的实现,我们针对MySQL数据库的实现进行说明。本文内容涉及MySQL中索引的语法索引的优缺点、索引的分类、索引的实现原理、索引的使用策略、索引的优化几部分。

    目录

    一、MySQL中索引的语法

    二、索引的优缺点

    三、索引的分类

    四、索引的实现原理

    1、哈希索引:

    2、全文索引:

    3、BTree索引和B+Tree索引

    *    聚簇索引和非聚簇索引

    五、索引的使用策略

    六、索引的优化


    一、MySQL中索引的语法

    创建索引

    在创建表的时候添加索引

    CREATE TABLE mytable(  
        ID INT NOT NULL,   
        username VARCHAR(16) NOT NULL,  
        INDEX [indexName] (username(length))  
    ); 

    在创建表以后添加索引

    ALTER TABLE my_table ADD [UNIQUE] INDEX index_name(column_name);
    或者
    CREATE INDEX index_name ON my_table(column_name);

    注意:

    1、索引需要占用磁盘空间,因此在创建索引时要考虑到磁盘空间是否足够

    2、创建索引时需要对表加锁,因此实际操作中需要在业务空闲期间进行

    根据索引查询

    具体查询:
    SELECT * FROM table_name WHERE column_1=column_2;(为column_1建立了索引)
    
    或者模糊查询
    SELECT * FROM table_name WHERE column_1 LIKE '%三'
    SELECT * FROM table_name WHERE column_1 LIKE '三%'
    SELECT * FROM table_name WHERE column_1 LIKE '%三%'
    
    SELECT * FROM table_name WHERE column_1 LIKE '_好_'
    
    如果要表示在字符串中既有A又有B,那么查询语句为:
    SELECT * FROM table_name WHERE column_1 LIKE '%A%' AND column_1 LIKE '%B%';
    
    SELECT * FROM table_name WHERE column_1 LIKE '[张李王]三';  //表示column_1中有匹配张三、李三、王三的都可以
    SELECT * FROM table_name WHERE column_1 LIKE '[^张李王]三';  //表示column_1中有匹配除了张三、李三、王三的其他三都可以
    
    //在模糊查询中,%表示任意0个或多个字符;_表示任意单个字符(有且仅有),通常用来限制字符串长度;[]表示其中的某一个字符;[^]表示除了其中的字符的所有字符
    
    或者在全文索引中模糊查询
    SELECT * FROM table_name WHERE MATCH(content) AGAINST('word1','word2',...);

    删除索引

    DROP INDEX my_index ON tablename;
    或者
    ALTER TABLE table_name DROP INDEX index_name;
    

    查看表中的索引

    SHOW INDEX FROM tablename

    查看查询语句使用索引的情况

    //explain 加查询语句
    explain SELECT * FROM table_name WHERE column_1='123';
    

    二、索引的优缺点

    优势:可以快速检索,减少I/O次数,加快检索速度;根据索引分组和排序,可以加快分组和排序;

    劣势:索引本身也是表,因此会占用存储空间,一般来说,索引表占用的空间的数据表的1.5倍;索引表的维护和创建需要时间成本,这个成本随着数据量增大而增大;构建索引会降低数据表的修改操作(删除,添加,修改)的效率,因为在修改数据表的同时还需要修改索引表;

    三、索引的分类

    常见的索引类型有:主键索引、唯一索引、普通索引、全文索引、组合索引

    1、主键索引:即主索引,根据主键pk_clolum(length)建立索引,不允许重复,不允许空值

    ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col');

    2、唯一索引:用来建立索引的列的值必须是唯一的,允许空值

    ALTER TABLE 'table_name' ADD UNIQUE index_name('col');

    3、普通索引:用表中的普通列构建的索引,没有任何限制

    ALTER TABLE 'table_name' ADD INDEX index_name('col');

    4、全文索引:用大文本对象的列构建的索引(下一部分会讲解)

    ALTER TABLE 'table_name' ADD FULLTEXT INDEX ft_index('col');

    5、组合索引:用多个列组合构建的索引,这多个列中的值不允许有空值

    ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3');

    *遵循“最左前缀”原则,把最常用作为检索或排序的列放在最左,依次递减,组合索引相当于建立了col1,col1col2,col1col2col3三个索引,而col2或者col3是不能使用索引的。

    *在使用组合索引的时候可能因为列名长度过长而导致索引的key太大,导致效率降低,在允许的情况下,可以只取col1和col2的前几个字符作为索引

    ALTER TABLE 'table_name' ADD INDEX index_name(col1(4),col2(3));

    表示使用col1的前4个字符和col2的前3个字符作为索引

    四、索引的实现原理

    MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,B+Tree索引,哈希索引,全文索引等等

    1、哈希索引:

    只有memory(内存)存储引擎支持哈希索引,哈希索引用索引列的值计算该值的hashCode,然后在hashCode相应的位置存执该值所在行数据的物理位置,因为使用散列算法,因此访问速度非常快,但是一个值只能对应一个hashCode,而且是散列的分布方式,因此哈希索引不支持范围查找和排序的功能。

    2、全文索引:

    FULLTEXT(全文)索引,仅可用于MyISAM和InnoDB,针对较大的数据,生成全文索引非常的消耗时间和空间。对于文本的大对象,或者较大的CHAR类型的数据,如果使用普通索引,那么匹配文本前几个字符还是可行的,但是想要匹配文本中间的几个单词,那么就要使用LIKE %word%来匹配,这样需要很长的时间来处理,响应时间会大大增加,这种情况,就可使用时FULLTEXT索引了,在生成FULLTEXT索引时,会为文本生成一份单词的清单,在索引时及根据这个单词的清单来索引。FULLTEXT可以在创建表的时候创建,也可以在需要的时候用ALTER或者CREATE INDEX来添加:

    //创建表的时候添加FULLTEXT索引
    CTREATE TABLE my_table(
        id INT(10) PRIMARY KEY,
        name VARCHAR(10) NOT NULL,
        my_text TEXT,
        FULLTEXT(my_text)
    )ENGINE=MyISAM DEFAULT CHARSET=utf8;
    //创建表以后,在需要的时候添加FULLTEXT索引
    ALTER TABLE my_table ADD FULLTEXT INDEX ft_index(column_name);

    全文索引的查询也有自己特殊的语法,而不能使用LIKE %查询字符串%的模糊查询语法

    SELECT * FROM table_name MATCH(ft_index) AGAINST('查询字符串');

    注意:

    *对于较大的数据集,把数据添加到一个没有FULLTEXT索引的表,然后添加FULLTEXT索引的速度比把数据添加到一个已经有FULLTEXT索引的表快。

    *5.6版本前的MySQL自带的全文索引只能用于MyISAM存储引擎,如果是其它数据引擎,那么全文索引不会生效。5.6版本之后InnoDB存储引擎开始支持全文索引

    *在MySQL中,全文索引支队英文有用,目前对中文还不支持。5.7版本之后通过使用ngram插件开始支持中文。

    *在MySQL中,如果检索的字符串太短则无法检索得到预期的结果,检索的字符串长度至少为4字节,此外,如果检索的字符包括停止词,那么停止词会被忽略。

    * 更深入的理解参考文章:全文索引的深入理解

     

    3、BTree索引和B+Tree索引

     

    • BTree索引

    BTree是平衡搜索多叉树,设树的度为2d(d>1),高度为h,那么BTree要满足以一下条件:

    • 每个叶子结点的高度一样,等于h;
    • 每个非叶子结点由n-1个keyn个指针point组成,其中d<=n<=2d,key和point相互间隔,结点两端一定是key;
    • 叶子结点指针都为null;
    • 非叶子结点的key都是[key,data]二元组,其中key表示作为索引的键,data为键值所在行的数据;

    BTree的结构如下:

    在BTree的机构下,就可以使用二分查找的查找方式,查找复杂度为h*log(n),一般来说树的高度是很小的,一般为3左右,因此BTree是一个非常高效的查找结构。

    BTree的查询、插入、删除过程可以参考:https://blog.csdn.net/endlu/article/details/51720299

    • B+Tree索引

    B+Tree是BTree的一个变种,设d为树的度数,h为树的高度,B+Tree和BTree的不同主要在于:

    • B+Tree中的非叶子结点不存储数据,只存储键值;
    • B+Tree的叶子结点没有指针,所有键值都会出现在叶子结点上,且key存储的键值对应data数据的物理地址;
    • B+Tree的每个非叶子节点由n个键值keyn个指针point组成;

    B+Tree的结构如下:

    B+Tree对比BTree的优点:

    1、磁盘读写代价更低

    一般来说B+Tree比BTree更适合实现外存的索引结构,因为存储引擎的设计专家巧妙的利用了外存(磁盘)的存储结构,即磁盘的最小存储单位是扇区(sector),而操作系统的块(block)通常是整数倍的sector,操作系统以页(page)为单位管理内存,一页(page)通常默认为4K,数据库的页通常设置为操作系统页的整数倍,因此索引结构的节点被设计为一个页的大小,然后利用外存的“预读取”原则,每次读取的时候,把整个节点的数据读取到内存中,然后在内存中查找,已知内存的读取速度是外存读取I/O速度的几百倍,那么提升查找速度的关键就在于尽可能少的磁盘I/O,那么可以知道,每个节点中的key个数越多,那么树的高度越小,需要I/O的次数越少,因此一般来说B+Tree比BTree更快,因为B+Tree的非叶节点中不存储data,就可以存储更多的key

    2、查询速度更稳定

    由于B+Tree非叶子节点不存储数据(data),因此所有的数据都要查询至叶子节点,而叶子节点的高度都是相同的,因此所有数据的查询速度都是一样的。

    更多操作系统内容参考:

    硬盘结构

    扇区、块、簇、页的区别

    操作系统层优化(进阶,初学不用看)

    • 带顺序索引的B+TREE

    很多存储引擎在B+Tree的基础上进行了优化,添加了指向相邻叶节点的指针,形成了带有顺序访问指针的B+Tree,这样做是为了提高区间查找的效率,只要找到第一个值那么就可以顺序的查找后面的值。

    B+Tree的结构如下:

     

    聚簇索引和非聚簇索引

    分析了MySQL的索引结构的实现原理,然后我们来看看具体的存储引擎怎么实现索引结构的,MySQL中最常见的两种存储引擎分别是MyISAM和InnoDB,分别实现了非聚簇索引和聚簇索引。

    聚簇索引的解释是:聚簇索引的顺序就是数据的物理存储顺序

    非聚簇索引的解释是:索引顺序与数据物理排列顺序无关

    这样说起来并不好理解,让人摸不着头脑,清继续看下文,并在插图下方对上述两句话有解释

    首先要介绍几个概念,在索引的分类中,我们可以按照索引的键是否为主键来分为“主索引”和“辅助索引”,使用主键键值建立的索引称为“主索引”,其它的称为“辅助索引”。因此主索引只能有一个,辅助索引可以有很多个。

    MyISAM——聚簇索引

    • MyISAM存储引擎采用的是非聚簇索引,非聚簇索引的主索引和辅助索引几乎是一样的,只是主索引不允许重复,不允许空值,他们的叶子结点的key都存储指向键值对应的数据的物理地址
    • 非聚簇索引的数据表和索引表是分开存储的。
    • 非聚簇索引中的数据是根据数据的插入顺序保存。因此非聚簇索引更适合单个数据的查询。插入顺序不受键值影响。
    • 只有在MyISAM中才能使用FULLTEXT索引。(mysql5.6以后innoDB也支持全文索引)

    *最开始我一直不懂既然非聚簇索引的主索引和辅助索引指向相同的内容,为什么还要辅助索引这个东西呢,后来才明白索引不就是用来查询的吗,用在那些地方呢,不就是WHERE和ORDER BY 语句后面吗,那么如果查询的条件不是主键怎么办呢,这个时候就需要辅助索引了。

    InnoDB——聚簇索引

    • 聚簇索引的主索引的叶子结点存储的是键值对应的数据本身,辅助索引的叶子结点存储的是键值对应的数据的主键键值。因此主键的值长度越小越好,类型越简单越好。
    • 聚簇索引的数据和主键索引存储在一起
    • 聚簇索引的数据是根据主键的顺序保存。因此适合按主键索引的区间查找,可以有更少的磁盘I/O,加快查询速度。但是也是因为这个原因,聚簇索引的插入顺序最好按照主键单调的顺序插入,否则会频繁的引起页分裂,严重影响性能。
    • 在InnoDB中,如果只需要查找索引的列,就尽量不要加入其它的列,这样会提高查询效率。

     

    *使用主索引的时候,更适合使用聚簇索引,因为聚簇索引只需要查找一次,而非聚簇索引在查到数据的地址后,还要进行一次I/O查找数据。

    *因为聚簇辅助索引存储的是主键的键值,因此可以在数据行移动或者页分裂的时候降低成本,因为这时不用维护辅助索引。但是由于主索引存储的是数据本身,因此聚簇索引会占用更多的空间。

    *聚簇索引在插入新数据的时候比非聚簇索引慢很多,因为插入新数据时需要检测主键是否重复,这需要遍历主索引的所有叶节点,而非聚簇索引的叶节点保存的是数据地址,占用空间少,因此分布集中,查询的时候I/O更少,但聚簇索引的主索引中存储的是数据本身,数据占用空间大,分布范围更大,可能占用好多的扇区,因此需要更多次I/O才能遍历完毕。

    下图可以形象的说明聚簇索引和非聚簇索引的区别

    从上图中可以看到聚簇索引的辅助索引的叶子节点的data存储的是主键的值,主索引的叶子节点的data存储的是数据本身,也就是说数据和索引存储在一起,并且索引查询到的地方就是数据(data)本身,那么索引的顺序和数据本身的顺序就是相同的;

    而非聚簇索引的主索引和辅助索引的叶子节点的data都是存储的数据的物理地址,也就是说索引和数据并不是存储在一起的,数据的顺序和索引的顺序并没有任何关系,也就是索引顺序与数据物理排列顺序无关。

     

    此外MyISAM和innoDB的区别总结如下:

    MyISAM和innoDB引擎对比
      MyISAM innoDB
    索引类型 非聚簇 聚簇
    支持事务
    支持表锁
    支持行锁 是(默认)
    支持外键
    支持全文索引 是(5.6以后支持)
    适用操作类型 大量select下使用 大量insert、delete和update下使用

    总结如下:

    • InnoDB 支持事务,支持行级别锁定,支持 B-tree、Full-text 等索引,不支持 Hash 索引;
    • MyISAM 不支持事务,支持表级别锁定,支持 B-tree、Full-text 等索引,不支持 Hash 索引;

    此外,Memory 不支持事务,支持表级别锁定,支持 B-tree、Hash 等索引,不支持 Full-text 索引;

    更多MyISAM和innoDB的区别具体内容参考:MyISAMheinnoDB的区别,包括行级锁死锁的具体分析

     

    五、索引的使用策略

     

    什么时候要使用索引?

    • 主键自动建立唯一索引;
    • 经常作为查询条件在WHERE或者ORDER BY 语句中出现的列要建立索引;
    • 作为排序的列要建立索引;
    • 查询中与其他表关联的字段,外键关系建立索引
    • 高并发条件下倾向组合索引;
    • 用于聚合函数的列可以建立索引,例如使用了max(column_1)或者count(column_1)时的column_1就需要建立索引

    什么时候不要使用索引?

    • 经常增删改的列不要建立索引;
    • 有大量重复的列不建立索引;
    • 表记录太少不要建立索引。只有当数据库里已经有了足够多的测试数据时,它的性能测试结果才有实际参考价值。如果在测试数据库里只有几百条数据记录,它们往往在执行完第一条查询命令之后就被全部加载到内存里,这将使后续的查询命令都执行得非常快--不管有没有使用索引。只有当数据库里的记录超过了1000条、数据总量也超过了MySQL服务器上的内存总量时,数据库的性能测试结果才有意义。

    索引失效的情况:

    • 在组合索引中不能有列的值为NULL,如果有,那么这一列对组合索引就是无效的。
    • 在一个SELECT语句中,索引只能使用一次,如果在WHERE中使用了,那么在ORDER BY中就不要用了。
    • LIKE操作中,'%aaa%'不会使用索引,也就是索引会失效,但是‘aaa%’可以使用索引。
    • 在索引的列上使用表达式或者函数会使索引失效,例如:select * from users where YEAR(adddate)<2007,将在每个行上进行运算,这将导致索引失效而进行全表扫描,因此我们可以改成:select * from users where adddate<’2007-01-01′。其它通配符同样,也就是说,在查询条件中使用正则表达式时,只有在搜索模板的第一个字符不是通配符的情况下才能使用索引。
    • 在查询条件中使用不等于,包括<符号、>符号和!=会导致索引失效。特别的是如果对主键索引使用!=则不会使索引失效,如果对主键索引或者整数类型的索引使用<符号或者>符号不会使索引失效。(经erwkjrfhjwkdb同学提醒,不等于,包括&lt;符号、>符号和!,如果占总记录的比例很小的话,也不会失效)
    • 在查询条件中使用IS NULL或者IS NOT NULL会导致索引失效。
    • 字符串不加单引号会导致索引失效。更准确的说是类型不一致会导致失效,比如字段email是字符串类型的,使用WHERE email=99999 则会导致失败,应该改为WHERE email='99999'。
    • 在查询条件中使用OR连接多个条件会导致索引失效,除非OR链接的每个条件都加上索引,这时应该改为两次查询,然后用UNION ALL连接起来。
    • 如果排序的字段使用了索引,那么select的字段也要是索引字段,否则索引失效。特别的是如果排序的是主键索引则select * 也不会导致索引失效。
    • 尽量不要包括多列排序,如果一定要,最好为这队列构建组合索引;

     

    六、索引的优化

     

    1、最左前缀

    索引的最左前缀和和B+Tree中的“最左前缀原理”有关,举例来说就是如果设置了组合索引<col1,col2,col3>那么以下3中情况可以使用索引:col1,<col1,col2>,<col1,col2,col3>,其它的列,比如<col2,col3>,<col1,col3>,col2,col3等等都是不能使用索引的。

    根据最左前缀原则,我们一般把排序分组频率最高的列放在最左边,以此类推

    2、带索引的模糊查询优化

    在上面已经提到,使用LIKE进行模糊查询的时候,'%aaa%'不会使用索引,也就是索引会失效。如果是这种情况,只能使用全文索引来进行优化(上文有讲到)。

    3、为检索的条件构建全文索引,然后使用

    SELECT * FROM tablename MATCH(index_colum) ANGAINST(‘word’);

    4、使用短索引

    对串列进行索引,如果可能应该指定一个前缀长度。例如,如果有一个CHAR(255)的 列,如果在前10 个或20 个字符内,多数值是惟一的,那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。

     

    展开全文
  • 1 索引的概念 索引是一个单独的、物理的数据库结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。表的存储由两部分组成,一部分用来存放数据页面,另一部分存放索引...

    1 索引的概念

    索引是一个单独的、物理的数据库结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。表的存储由两部分组成,一部分用来存放数据页面,另一部分存放索引页面。通常,索引页面相对于数据页面来说小得多。数据检索花费的大部分开销是磁盘读写,没有索引就需要从磁盘上读表的每一个数据页,如果有索引,则只需查找索引页面就可以了。所以建立合理的索引,就能加速数据的检索过程。

    SQL Server采用B-树结构的索引,根据索引的顺序与数据表的物理顺序是否相同可以分为:聚簇索引(clustered index)和非聚簇索引(nonclustered index)。

    (1)聚簇索引重新组织表中的数据以按指定的一个或多个列的值排序。聚簇索引的叶节点包含实际的数据,因此用它查找数据很快,但每个表只能建一个聚簇索引。

    (2)非聚簇索引不重新组织表中的数据,它的叶节点中存储了组成非聚簇索引的列的值和行定位指针。一个表可以建249 个非聚簇索引。

    通俗的说,汉语字典的正文就是一个建立在拼音基础上的聚簇索引,以英文字母“a”开头并以“z”结尾。比如,我们要查“阿”字,就会翻开字典的第一页,因为“阿”的拼音是“a”,所以排在字典的前面。如果您翻完了所有以“a”开头的部分仍然找不到这个字,那么就说明字典中没有这个字。同样的,如果查“做”字,就会把字典翻到最后。

    字典的“偏旁部首”是非聚簇索引。比如我们要查“阿”字,在查部首之后,看到部首检字表中“阿”的页码是1页,“阿”的上面是“际”字,但页码却是277页,“阿”的下面是“陇”字,页码是416页。很显然,这些字并不是真正的分别位于“阿”字的上下方,现在看到的连续的“际、阿、陇”三字实际上就是他们在非聚簇索引中的排序,是字典正文中的字在非聚簇索引中的映射。

    2 索引的使用

    1)聚簇索引的使用

    在聚簇索引下,数据在物理上按顺序排在数据页上,重复值也排在一起,因而在那些包含范围检查(between、<、<=、>、>=)或使用group by、order by的查询时,一旦找到具有范围中第一个键值的行,具有后续索引值的行必然连在一起,不必进一步搜索,避免了大范围扫描,可以大大提高查询速度。

    聚簇索引的侯选列是:

    u        经常按范围存取的列,如date>”20050101” and date< “20050131”;

    u        经常在where子句中使用并且插入是随机的主键列;

    u        在group by或order by中使用的列;

    u        在连接操作中使用的列。

    2)非聚簇索引的使用

    由于非聚簇索引的叶级点不包含实际的数据,因此它检索效率较低,但一个表只能建一个聚簇索引,当用户需要建立多个索引时就需要使用非聚簇索引了。在建立非聚簇索引时,要权衡索引对查询速度的加快与降低修改速度之间的利弊。

    在下面情况中使用非聚簇索引:

    u        常用于集合函数(如Sum,....)的列;

    u        常用于join, order by, group by的列;

    u        查寻出的数据不超过表中数据量的20%。

    3)创建索引需要注意的要点

    1)    慎重选择作为聚簇索引的列

    默认情况下,SQL Server用主键创建聚簇索引。这种做法常常造成聚簇索引的浪费。通常,我们会为每个表建立一个ID列,以区分每条数据,并且该列是自动增大的,步长一般为1。如果我们把这个列设为主键,SQL Server会将此列默认为聚簇索引。这样做可以使数据在数据库中按ID进行物理排序,但这种做法在实际应用中意义并不大。根据前面谈到的聚簇索引的定义和使用情况可以看出,使用聚簇索引的最大好处就是能够根据查询要求,迅速返回某个范围内的数据,避免全表扫描。在实际应用中,因为ID号是自动生成的,我们并不知道每条记录的ID号,所以我们不太可能用ID号来进行查询。这就使聚簇索引成为摆设,造成资源浪费。其次,让每个值都不同的ID列作为聚簇索引也不符合“大数目的不同值情况下不应建立聚簇索引”规则。

    一般情况下,数据库应用系统进行数据检索都离不开“ 用户名(代码)”、“日期”字段。以笔者所用的HIS系统(医院管理信息系统)为例,我们进行费用、处方、检查单等信息检索时需要根据“住院号”和“日期”这两个字段来返回特定范围内的数据。下面我们分几种情况观察在不同索引条件下查询相同内容所用的时间。

    假设病人费用表名为“brfy”,其中住院号字段名为“zyh”,日期字段名为“riqi”,要求是从表brfy中检索zyh为“028246”的病人2005年3月1日到20日的费用,对应的SQL语句如下:

    Select * from brfy where zyh=’028246’ and riqi>=’20050301’ and riqi<=’20050320’;

    第一种情况,用ID列建立聚簇索引,不为zyh和riqi建立索引,查询时间为87秒。

    第二种情况,用ID列建立聚簇索引,为zyh和riqi两列建立非聚簇索引(zyh在前),查询时间为33秒。

    第三种情况,用zyh和riqi两列建立聚簇索引(zyh在前),查询时间为2秒。

    由以上分析可以看出聚簇索引是非常宝贵的,应该为经常用于检索某个范围内数据的列或group by、order by等子句的列建立聚簇索引,这样能够极大的提高系统性能。

    2)    重视以多个列创建的索引中列的顺序问题

    一些用户认为只要合理的选择列建立索引,不必关心列的顺序就可以提高检索速度,这种观点是错误的。多列索引中列的先后顺序应该和实际应用中where、group by或order by等子句里列的放置位置相同。参考上面举的例子,在第二、第三种情况下,如果把riqi放在zyh前面,执行上述SQL语句就不会用到这两个索引,检索的时间也会变得很长。

    3 索引的维护

    数据库系统运行一段时间后,随着数据行的插入、删除和数据页的分裂,索引对系统的优化性能就会大大降低。这时候,我们需要对索引进行分析和重建。

    SQL Server使用DBCC SHOWCONTIG确定是否需要重建表的索引。在 SQL Server的查询分析器中输入命令:

    Use database_name

    Declare @table_id int

    Set @table_id=object_id ('Employee')

    Dbcc showcontig (@table_id)

    在命令返回的参数中Scan Density 是索引性能的关键指示器,这个值越接近100%越好,一般在低于90%的情况下,就需要重建索引。重建索引可以使用DBCC DBREINDEX,使用方式如下:

    dbcc dbreindex('表名', 索引名, 填充因子)       /*填充因子一般为90或100*/

    如果重建后,Scan Density还没有达到100%,可以重建该表的所有索引:

    dbcc dbreindex('表名', '', 填充因子)

    在良好的数据库设计基础上,有效地使用索引是数据库应用系统取得高性能的基础。然而,任何事物都具有两面性,索引也不例外。索引的建立需要占用额外的存储空间,并且在增、删、改操作中也会增加一定的工作量,因此,在适当的地方增加适当的索引并从不合理的地方删除次要的索引,将有助于优化那些性能较差的数据库应用系统。实践表明,合理的索引设计是建立在对各种查询的分析和预测上的,只有正确地使索引与程序结合起来,才能产生最佳的优化方案。


    1.创建表并插入数据

    在Sql Server2008中创建测试数据库Test,接着创建数据库表并插入数据,sql代码如下:

    复制代码
    USE Test
    IF EXISTS (SELECT * FROM INFORMATION_SCHEMA.TABLES 
          WHERE TABLE_NAME = 'emp_pay')
       DROP TABLE emp_pay
    GO
    USE Test
    IF EXISTS (SELECT name FROM sys.indexes 
          WHERE name = 'employeeID_ind')
       DROP INDEX emp_pay.employeeID_ind
    GO
    USE Test
    GO
    CREATE TABLE emp_pay
    (
     employeeID int NOT NULL,
     base_pay money NOT NULL,
     commission decimal(2, 2) NOT NULL
    )
    INSERT emp_pay
       VALUES (1, 500, .10)
    INSERT emp_pay 
       VALUES (2, 1000, .05)
    INSERT emp_pay 
       VALUES (6, 800, .07)
    INSERT emp_pay
       VALUES (5, 1500, .03)
    INSERT emp_pay
       VALUES (9, 750, .06)
    复制代码

    执行完上述sql代码以后我们会发现在Test数据库中多出了一张emp_pay表,数据库表的内容如下图所示:

    2.无索引查找

    从上图我们可以看出数据库中存储的数据排列顺序与我们插入的先后顺序一致。接下来我们查询employeeID=5的字段,执行如下sql代码:

    USE Test
    SELECT * FROM emp_pay where employeeID=5

    在SQL SERVER MANAGEMENT STUDIO中我们点击“显示估计的查询计划”,会出现如下图所示的查询计划图:

    其中表扫描的内容为:

    3.创建索引

    接下来我们为上述表添加聚集唯一索引,代码如下:

    SET NOCOUNT OFF
    CREATE UNIQUE CLUSTERED INDEX employeeID_ind
       ON emp_pay (employeeID)
    GO

    在执行完上述创建索引的代码以后,我们再次查询emp_pay的数据内容,如下图所示:

    从上图我们可以发现数据内容已经按照employeeID进行了排序。

    我们继续执行前面关于employeeID=5的查询,点击“显示估计的执行计划”,出现如下图所示内容:

    聚集索引查找的内容为:

    总结:

    当我们为数据库表中的某一个字段创建索引,并且在查询语句中where子句中用到这样一个字段,那么查询效率会有所提高,我们上述实验因为数据量的关系查询效率提高不明显。

    补充

    我们上面添加的索引是唯一聚集索引,因此当插入的数据在employeeID字段出现重复时会报错。假如我们在创建索引之前数据字段出现重复,那么就不能创建唯一索引。

    创建索引以后的排序(PS:2012-5-28)

    执行如下sql语句

    update emp_pay set employeeID=7 where employeeID=1;

    然后再次执行全表查询,我们发现查询结果如下所示:

    只要我们更新了employeeID,那么最后的更新结果都会按照employeeID的值进行升序排序。这是因为我们在employeeID上创建了索引的缘故。

    删除索引(PS:2012-6-4)

    我们可以通过sql server management studio这个工具删除索引,也可以通过sql语句进行索引的删除,假设我们要求删除在前面创建的索引employeeID_ind,那么sql语句如下代码所示:

    DROP INDEX employeeID_ind ON emp_pay;

    展开全文
  • 数据库索引

    2019-02-22 09:18:43
    说白了,数据库的索引问题就是查找问题 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询,更新数据库中表的数据.索引的实现通常使用B树和变种的B+树(mysql常用的索引就是B+树) 除了数据之外,数据库...
  • 索引失效和注意事项

    2018-08-25 14:45:15
    如果是同样的sql如果在之前能够使用到索引,那么现在使用不到索引,以下几种主要情况: 随着表的增长,where条件出来的数据太多,大于15%,使得索引失效(会导致CBO计算走索引花费大于走全表) 统计信息失效 ...
  • 索引是表的目录,在查找内容之前可以先在目录中查找索引位置,以此快速定位查询数据。对于索引,会保存在额外的文件中。 2、索引,是数据库中专门用于帮助用户快速查询数据的一种数据结构。类似于字典中的目录,...
  • 一、索引是什么 索引是与表或视图关联的磁盘上结构,可以加快从表或视图中检索行的速度。索引包含由表或视图中的一列或多列生成的键。这些键存储在一个结构(B树)中,使 SQL Server 可以快速有效地查找与键值...
  • 关于MySQL索引的好处,如果正确合理设计并且使用索引的MySQL是一辆兰博基尼的话,那么没有设计和使用索引的MySQL就是一个人力三轮车。对于没有索引的表,单表查询可能几十万数据就是瓶颈,而通常大型网站单日就可能...
  • 那么当查询条件为2个及以上时,我们是创建多个单列索引还是创建一个联合索引好呢?他们之间的区别是什么?哪个效率高呢?我在这里详细测试分析下。 一、联合索引测试 注:Mysql版本为 5.7.20 创建测试表(表记录...
  • 一、索引MySQL索引的建立对于MySQL的高效运行是很重要的,索引可以大大提高MySQL的检索速度。打个比方,如果合理的设计且使用索引的MySQL是一辆兰博基尼的话,那么没有设计和使用索引的MySQL就是一个人力三轮车。...
  • 说白了,索引问题就是一个查找问题。。。 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。 在数据之外,数据库系统还维护着...
  • MySQL索引类型一览 让MySQL高效运行起来 本文介绍了七种MySQL索引类型。在数据库表中,对字段建立索引可以大大提高查询速度。通过善用这些索引,可以令MySQL的查询和运行更加高效。 索引是快速搜索的关键。MySQL...
  • 特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常...
  • MongoDB 提供了多样性的索引支持,索引信息被保存在system.indexes 中,且默认总是为_id创建索引,它的索引使用基本和MySQL 等关系型数据库一样。其实可以这样说说,索引是凌驾于数据存储系统之上的另一层系统,所以...
  • 数据库的索引,听起来挺神秘的,仔细想想。这些索引,其实就是平时咱们查东西时候常用的两种手段。无非就是为了提高我们找东西的效率而已。那么我们平时又是怎么查东西呢? 聚集索引: 聚集索引,来源于生活尝试。...
  • 聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。 一般情况下主键会默认创建聚簇索引,且一张表只允许存在一个聚簇索引。 在《数据库原理》一书中...
  • 目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,...
  • Mysql索引整理总结

    2019-08-10 20:55:52
    一、索引概述 1. 简介 索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。 举例说明索引:如果把数据库中的某一张看成一本书,那么索引就像是书的目录,可以通过...
1 2 3 4 5 ... 20
收藏数 1,747,145
精华内容 698,858
关键字:

索引