索引_索引mysql - CSDN
索引 订阅
在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录,可以根据目录中的页码快速找到所需的内容。索引提供指向存储在表的指定列中的数据值的指针,然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值,然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快,可快速访问数据库表中的特定信息。当表中有大量记录时,若要对表进行查询,第一种搜索信息方式是全表搜索,是将所有记录一一取出,和查询条件进行一一对比,然后返回满足条件的记录,这样做会消耗大量数据库系统时间,并造成大量磁盘I/O操作;第二种就是在表中建立索引,然后在索引中找到符合查询条件的索引值,最后通过保存在索引中的ROWID(相当于页码)快速找到表中对应的记录。 展开全文
在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录,可以根据目录中的页码快速找到所需的内容。索引提供指向存储在表的指定列中的数据值的指针,然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值,然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快,可快速访问数据库表中的特定信息。当表中有大量记录时,若要对表进行查询,第一种搜索信息方式是全表搜索,是将所有记录一一取出,和查询条件进行一一对比,然后返回满足条件的记录,这样做会消耗大量数据库系统时间,并造成大量磁盘I/O操作;第二种就是在表中建立索引,然后在索引中找到符合查询条件的索引值,最后通过保存在索引中的ROWID(相当于页码)快速找到表中对应的记录。
信息
作    用
应于表的SQL语句执行得更快
分    类
数据库概念
中文名
索引
外文名
index
索引发展历史
旧称通检、备检或引得。组成的基本单位是索引款目。款目一般包括索引词、说明或注释语 、出处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。

    展开全文
  • 数据库索引

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

    引言

    说白了,数据库的索引问题就是查找问题

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

    除了数据之外,数据库系统还维护为满足特定查找算法的数据结构,这些数据结构以某种方式引用数据.这种数据结构就是索引

    创建索引的好处

    ①通过创建索引,可以在查询的过程中,提高系统的性能

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

    ③在使用分组和排序子句进行数据检索时,可以减少查询中分组和排序的时间

    创建索引的坏处

    ①创建索引和维护索引要耗费时间,而且时间随着数据量的增加而增大

    ②索引需要占用物理空间,如果要建立聚簇索引,所需要的空间会更大

    ③在对表中的数据进行增加删除和修改时需要耗费较多的时间,因为索引也要动态地维护

    应该在哪些列上创建索引呢

    ①经常需要搜索的列上

    ②作为主键的列上

    ③经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度

    ④经常需要根据范围进行搜索的列上

    ⑤经常需要排序的列上

    ⑥经常使用在where子句上面的列上

    不应该在哪些列上创建索引

    ①查询中很少用到的列

    ②对于那些具有很少数据值的列.比如人事表的性别列,bit数据类型的列

    ③对于那些定义为text,image的列.因为这些列的数据量相当大

    ④当对修改性能的要求远远大于搜索性能时.因为当增加索引时,会提高搜索性能,但是会降低修改性能

    索引的分类和使用

    按物理存储角度分:

    聚集索引

    表记录的排列顺序和索引的排列顺序一致,所以查询效率快,只要找到第一个索引值记录,其余连续性的记录在物理上一样连续存放.聚集索引的缺点就是修改慢,因为为了使表记录和索引的排列顺序一致,在插入记录的时候,会对数据页重新排序

    非聚集索引

    表记录和索引的排列顺序不一定一致,两种索引都采用B+树的结构,非聚集索引的叶子层并不和实际数据页相重叠,而采用叶子层包含一个指向表记录的指针.非聚集索引层次多,不会造成数据重排

    按逻辑角度分

    2)普通索引,最基本的索引,它没有任何的限制

    4)复合索引(又叫做多列索引,联合索引):多个字段上建立的索引,提高复合条件查询的速度

    创建联合索引:create index idx_name_age on student(name,age);

    查看索引:show index from student;

    数据库索引在什么情况下失效

    (1)条件中用or(这就是为什么少用or的原因)

    (2)

    对于多列(复合、联合)索引,不是使用的第一部分,则不会使用索引。(最左匹配原则或者叫做最左前缀原则)

    比如:Index_SoftWareDetail索引包含(a,b,c) 三列,但是查询条件里面,没有a,b 列,只有c 列,那么 Index_SoftWareDetail索引也不起作用

    例如:bc   c   acb bac 都是不行的

    (3)like的模糊查询以%开头,索引失效

    (4)如果列类型是字符串,那一定要在条件中将数据使用引号引用起来,否则不会使用索引

    (5)如果MySQL预计使用全表扫描要比使用索引快,则不使用索引

    (6)判断索引列是否不等于某个值时。‘!=’操作符。比如:select * from SoftWareDetailInfo where SoftUseLine != 0

    (7)

    对索引列进行运算。这里运算包括+-*/等运算。也包括使用函数。比如:

    select * from SoftWareDetailInfo where SoftUseLine +0= 0

    此时索引不起作用。

    select * from SoftWareDetailInfo where count(SoftUseLine) = 0

    此时索引也不起作用。

    也就是说如果不是直接判断索引字段列,而是判断运算或其它函数处理后的索引列索引均不起作用。

    (8)索引字段进行判空查询时。也就是对索引字段判断是否为NULL时。语句为is null 或is not null。

      比如:select * from SoftWareDetailInfo where CreateTime is null 此时就不检索time字段上的索引表了。也就是索引在这条语句执行时失效了。

      接着再执行

    select * from SoftWareDetailInfo where CreateTime = '2015-04-11 00:00:00' 此时就会检索索引表了。索引又起作用了。

    (9)范围列可以用到索引(联合索引必须是最左前缀),但是范围列后面的列无法用到索引

    索引的优化

    ①尽量不要使用左模糊和全模糊,如果需要可以使用搜索引擎来解决

    ②union,in和or都可以命中索引,建议使用in

    ③负向条件查询不能使用索引,可以优化为in查询

    负向条件查询有:!=  <>  not in  not like等等

    例如:select * from user where status!=1 and status!=2

    优化为:select * from user where status in (0,3,4);

    ④合理使用联合索引的最左前缀原则

    如果在(a,b,c)三个字段上建立联合索引,那么它能够加快 a | (a,b) | (a,b,c) 三组查询速度。

    比如说把(username,password)建立了联合索引,因为业务上几乎没有password的单条件查询,而有很多username的单条件查询需求,所以应该建立(username,password)的联合索引,而不要建立(password,username)的联合索引

    注意:(1)建立联合索引的时候,要把查询频率较高的列放在最左边

    (2)如果建立了(a,b)索引,就不必再独立建立a索引。同理如果建立了(a,b,c)联合索引,就不必再独立建立a,(a,b)索引

    (3)存在非等号和等号混合判断条件时,在建索引时,请把等号条件的列前置。如     where a>? and b=?,那么即使 a 的区分度更高,也必须把 b 放在索引的最前列。

    (4)最左前缀原则,并不是要求where后的顺序和联合索引的一致。下面的 SQL 语句也可以命中 (login_name, passwd) 这个联合索引。

    • selectuid, login_time from user where passwd=? andlogin_name=?

    但还是建议 where 后的顺序和联合索引一致,养成好习惯。

    ⑤把计算放到业务层而不是数据库层。(因为对索引列进行运算,不能命中索引)

    ⑥表数据比较少、更新十分频繁、数据区分度不高的字段上不宜建立索引。

    一般区分度在80%以上的时候就可以建立索引,区分度可以使用 count(distinct(列名))/count(*) 来计算。

    ⑦强制类型转换会全表扫描

    例如:如果phone字段是varchar类型,则下面的sql不能命中索引

    select * from user where phone = 18838003017

    可以优化为:select * from user where phone = ‘18838003017’

    ⑧利用覆盖索引进行查询操作,避免回表

    select uid,login_time from user where username=? and password=?

    如果建立了(username,password,login_time)的联合索引,由于login_time已经建立在索引中了,被查询的username和password就不用去row上获取数据了,从而加速查询

    ⑨在order by和group by中要注意索引的有序性

    如果order by是组合索引的一部分,应该将该字段放在组合索引的最后

    例如:where a=? and b=? order by c ->可以建立联合索引(a,b,c)

    如果索引中有范围查找,则索引的有序性无法利用

    例如:where a>10 order by b ->索引(a,b)无法排序

    ⑩建立索引的列,不许为null

    单列索引不存 null 值,复合索引不存全为 null 的值,如果列允许为 null,可能会得到“不符合预期”的结果集,所以,请使用 not null 约束以及默认值。

    sql语句的优化

    ①能用到索引尽量用到索引.对索引的优化实际上就是sql语句的调优

    ②任何地方都不要使用 select * from t ,用具体的字段列表代替“*”,不要返回用不到的任何字段。

    ③尽量使用where,而不要使用having

    ④尽量使用多表查询,不要使用子查询

    ⑤where后的and.or左右执行顺序是从右至左

    运算符为and时--尽量把为假的放在右边

    运算符为or时--尽量把为真的放在右边

     

     

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

    千次阅读 2018-08-25 14:45:15
    如果是同样的sql如果在之前能够使用到索引,那么现在使用不到索引,以下几种主要情况: 随着表的增长,where条件出来的数据太多,大于15%,使得索引失效(会导致CBO计算走索引花费大于走全表) 统计信息失效 ...
  • 索引的概念和创建索引例子

    千次阅读 2017-06-29 15:36:57
    1 索引的概念 索引是一个单独的、物理的数据库结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。表的存储由两部分组成,一部分用来存放数据页面,另一部分存放索引...
  • 什么是索引?Mysql目前主要的几种索引类型

    万次阅读 多人点赞 2018-02-27 10:11:16
    一、索引MySQL索引的建立对于MySQL的高效运行是很重要的,索引可以大大提高MySQL的检索速度。打个比方,如果合理的设计且使用索引的MySQL是一辆兰博基尼的话,那么没有设计和使用索引的MySQL就是一个人力三轮车。...
  • 数据库索引原理,及MySQL索引类型

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

    千次阅读 2019-04-04 16:00:09
    一、索引 MySQL索引的建立对于MySQL的高效运行是很重要的,索引可以大大提高MySQL的检索速度。 打个比方,如果合理的设计且使用索引的MySQL是一辆兰博基尼的话,那么没有设计和使用索引的MySQL就是一个人力三轮车...
  • 文章目录索引索引索引设置索引名查看索引的类重复索引通过索引查找数据查看索引处理重复索引多级索引创建索引(双层索引:行索引与列索引)行列索引转换通过索引查找数据不同等级索引转换根据索引求和设置索引值 ...
  • 点击链接 普通索引 唯一索引 全文索引 组合索引 ...
  • http://blog.csdn.net/douunderstand/article/details/70215061
  • 普通索引:最基本的索引,没有任何限制 唯一索引:与"普通索引"类似,不同的就是:索引列的值必须唯一,但允许有空值。 主键索引:它 是一种特殊的唯一索引,不允许有空值。  全文索引:仅可用于 MyISAM ...
  • 单列索引和联合索引的区别

    千次阅读 2018-09-28 09:49:54
    多个单列索引和联合索引的区别详解 单列索引和联合索引的区别
  • 聚集索引和覆盖索引

    2020-07-24 00:34:03
    聚集索引和覆盖索引 索引 表的数据量比较大时,查询操作会很耗时。建立索引是加快查询速度的有效手段。 数据库索引就类似于书签,可以快速定位到要查询的内容。数据库索引类型 有顺序文件索引,B+树索引,散列索引...
  • 普通索引 最基本的索引类型,没有唯一性之类的限制。普通索引可以通过以下几种方式创建: 创建索引,例如CREATE INDEX ON tablename (列的列表); 修改表,例如ALTER TABLE tablename ADD INDEX [索引的名字] (列...
  • 普通索引:index仅仅是加快查询速度主键索引:primary key不能重复,主键至多只有一个唯一索引:unique index行上的值不能重复全文索引:fulltext index建立索引alter table buy add index index1(sum);alter table ...
  • oracle 组合索引和单列索引实践

    千次阅读 2019-03-22 14:22:15
    http://note.youdao.com/noteshare?id=96ae67d24dd00cc18dcc33367bf7c21a
  • 稀疏索引:文件只为索引码的某些值建立索引项, 比如 innodb的其他索引只存了键位信息和主键, myisam的所有索引都是 聚簇索引: 表数据按顺序存储,即索引顺序和表记录物理存储顺序一致。 聚簇索引 叶子节点...
1 2 3 4 5 ... 20
收藏数 1,781,548
精华内容 712,619
关键字:

索引