精华内容
下载资源
问答
  • mysql索引索引存储结构

    千次阅读 2020-06-22 17:03:20
    文章目录什么是索引索引存储结构如果使用有序数组如果使用单链表如果使用二分查找树(Binary Search Tree)平衡二叉树(AVL树)多路平衡查找树(B Trees)加强版多路平衡树(B+ Trees)简单了解HASH索引 ...


    前言:首先推荐一个数据结构可视化的网站: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html,本文不做过深的数据结构剖析,但是要简单了解一些数据结构的特性和概念。
    了解索引的存储结构前,我们必须要先了解一些索引的基本概念。

    什么是索引

    索引:就是数据库管理系统中一个排序的数据结构,协助快速查询和更新表中数据。注意索引是放在磁盘上的
    建立索引的方式:
    1.建表的时候就创建
    2.建完表后续想添加索引:alter table 表名 add index 索引名(字段名);
    索引的类型:
    1.normal:普通索引,非唯一的索引没有任何限制
    2.unique:唯一索引,要求字段的值不能重复。(primary key主键索引,特殊的唯一索引,主键索引所在的列字段必须NOT NULL)
    3.full Text:全文索引,如果要在一个大文本里匹配一个字符那么就可以创建一个全文索引。char、varchar、text这些类型才能创建全文索引,匹配语法:select * from 表名 where match(字段名) against(‘要匹配的字符’ in natural language mode);

    索引的存储结构

    我们都知道mysql中的索引有BTREE和HASH,而最常使用的就是BTREE。那么问题来了,为什么mysql当初的设计者要选择使用B树呢?

    如果使用有序数组

    我们知道数组有下标,像’=’,’>’,’<'这些查询效率会很高,但是,更新索引时就会出现挪动大量数据,改变数据下标,所以这并不适合作为mysql的存储结构。

    如果使用单链表

    针对上边问题,我们会先想到使用链表来解决更新问题,因为链表记录的有上个节点和下个节点的地址。但是看,插入和更新快了,他的查询效率大大减少,因为单链表不支持二分查询,所以说查询效率是很低的。那么有没有使用二分查找的链表呢?

    如果使用二分查找树(Binary Search Tree)

    二分查找树简称BST
    特点:左子树的值都要小于父节点,右子树的值都要大于父节点。
    缺点:如图所示,如果是有序的插入,那么BST树就会变成一个线性的链表(斜树,不平衡树),深度会很大。导致查询会很慢。所以也并不适合mysql的索引结构

    在这里插入图片描述

    平衡二叉树(AVL树)

    AVL也就是发明者的名字简写。
    特点:基于二叉树,但左右子树的深度差得绝对值不超过1。如果右子树的深度和左子树的深度绝对值超过1,就会发生左旋(反之右旋),如下图:
    在这里插入图片描述
    缺点:如果mysql采用这种方式存储索引,那么我们看下图存储示例:
    在这里插入图片描述
    假设我们要找37这条数据,我们去索引树上找,第一次拿到磁盘块1之后,要到server层来比较发现我们要找的数据比他大,就到右子树上找下个磁盘块,继续比较发现又小了,就继续到左子树找下个磁盘块。才拿到所需数据。

    我们要知道,我们每次访问树节点的时候就是和磁盘的一次IO,将磁盘数据加载进内存。前边文章说过,在InnoDB中,IO操作的最小单位是页(page),默认是16kb。但是,如上图,一个节点只存储了那么点东西,是远远不够16kb的(16384个字节),所以说,使用AVL树每次IO都会浪费大量的空间,而且放的节点越多,IO次数也就越多,浪费的空间也就越大,所需时间也越多

    比如上图中,要查找37这条数据,就要3次IO,如果有成千上万条数据呢,IO时间是无法估量的。
    思考一下如何解决这一问题呢?我们可以让每个节点存储更多的数据,可以让二叉变成多叉(“叉数”也就是“路数”也称为“度”) ,这样可以让树的深度减少,IO次数也就越少,查询速度也就越快。

    多路平衡查找树(B Trees)

    我们来看,和上图同样的数据,在B树中要找37这条数据,如下图,只需要两次IO就可以了。数据量越大效果也就越明显。
    在这里插入图片描述
    那么这个B树是如何实现一个节点存储多个数据并且还保持平衡的呢?
    分裂和合并:假如路数是3,也就是一个节点只能放两个数据,如果要插入第三个数据即路数即将超过3,将会产生分裂(反之合并)。如下图:
    在这里插入图片描述
    mysql中索引用的B树,并不是该B树,而是用的增强版的B+树,接下来我们了解一下,什么是B+树。

    加强版多路平衡树(B+ Trees)

    特点:和B树不同的是
    1.B+树的节点上有几个数据,就有几路。
    2.每个父节点的元素都会出现在子节点上,是子节点的最大或最小元素。
    3.只有叶子节点才存储数据,并且每个叶子节点都有指向下一个节点的指针,形成一个有序链表。
    在这里插入图片描述
    我们来看一看B+树 有多强大:
    假设存储bigint类型(8bytes),InnoDB中的指针大小为6bytes,所以这样的一个索引就是14个字节,每个节点16kb(16384个字节),那么一个节点就可以存放16384/14=1170路。那么子节点就可以存放11701170=1368900个索引也就有1368900路。那么假设一条数据1k,一个叶子节点16k可以存放16条记录,那么1368900路的叶子节点共可以存放136890016=21902400条记录,也就是两千多万条记录,树的深度只有2,查找数据只需三次IO。

    不仅如此,B+树叶子节点还是一个有序的链表,如果我们进行范围的查找,如where id> 18 and id < 30,这种的条件查询,如果是B树他每次都会在根节点开始遍历查找,而B+树一次查找就可以沿着叶子节点的链表指针检索出所需数据。

    B+树的优势:
    1.单一节点存储更多的元素,使得查询的IO次数更少。
    2.所有查询都要查找到叶子节点,查询性能稳定。
    3.所有叶子节点形成有序链表,便于范围查询。

    简单了解HASH索引

    因为hash索引用的并不多,简单了解下:
    hash方式在我们的索引里面去存储了键值和映射关系,会根据索引的字段去生成hash码和指针,指针指向数据,他的时间复杂度是永恒不变的O(1),查询速度很快。
    不足之处:
    1.生成hash码是无序的
    2.只能做等值的查询,因为它要根据键计算出hash码,所以只能是根据key去查value这种形式
    3.如果字段有很多重复的值,就会产生大量的hash冲突。
    所以一般不会使用hash方式作为索引的存储结构

    <<上一篇:InnoDB存储引擎的磁盘架构

    >>下一篇:mysql索引在存储引擎中的实现及索引的使用原则

    展开全文
  • Lucene索引存储结构

    2020-04-29 17:41:30
    索引文档的总体结构 索引(index):Lucene的索引由许多个文件组成,这些文件放在同一个目录下 段(segment):一个Lucene的索引由多个段组成,段与段之间是独立的。添加新的文档时可以生成新的段,达到阈值(段...

    内存管理 与 数据存储

    索引文档的总体结构

             索引(index):Lucene的索引由许多个文件组成,这些文件放在同一个目录下

             段(segment):一个Lucene的索引由多个段组成,段与段之间是独立的。添加新的文档时可以生成新的段,达到阈值(段的个数,段中包含的文件数等)时,不同的段可以合并。在文件夹下,具有相同前缀的文件属于同一个段segments.gen 和 segments_N(N表示一个具体数字,eg:segments_5)是段的元数据文件,他们保存了段的属性信息。

            文档(document):文档时建索引的基本单位,一个段中可以包含多篇文档。新添加的文档时单独保存在一个新生成的段中,随着段的合并,不同的文档会合并到至相同的段中。

             域(Field):一个文档有可由多个域(Field)组成,比如一篇新闻,有 标题,作者,正文等多个属性,这些属性可以看作是文档的域。不同的域可以指定不同的索引方式,比如指定不同的分词方式,是否构建索引,是否存储等

             词(Term):词 是索引的最小单位,是经过词法分词和语言处理后的字符串。

    Lucene的索引结构中,即保存了正向信息,也保存了反向信息。

    正向信息:

    按层次保存了从索引,一直到词的包含关系:索引(Index) –> 段(segment) –> 文档(Document) –> 域(Field) –> 词(Term)

    也即此索引包含了那些段,每个段包含了那些文档,每个文档包含了那些域,每个域包含了那些词。

    既然是层次结构,则每个层次都保存了本层次的信息以及下一层次的元信息,也即属性信息,比如一本介绍中国地理的书,应该首先介绍中国地理的概况,以及中国包含多少个省,每个省介绍本省的基本概况及包含多少个市,每个市介绍本市的基本概况及包含多少个县,每个县具体介绍每个县的具体情况。

    如上图,包含正向信息的文件有:

              segments_N保存了此索引包含多少个段,每个段包含多少篇文档。

              XXX.fnm保存了此段包含了多少个域,每个域的名称及索引方式。

              XXX.fdx,XXX.fdt保存了此段包含的所有文档,每篇文档包含了多少域,每个域保存了那些信息。

              XXX.tvx,XXX.tvd,XXX.tvf保存了此段包含多少文档,每篇文档包含了多少域,每个域包含了多少词,每个词的字符串,位置等信息。

    反向信息:

    保存了词典到倒排表的映射:词(Term) –> 文档(Document)

    如上图,包含反向信息的文件有:

              XXX.tis,XXX.tii保存了词典(Term Dictionary),也即此段包含的所有的词按字典顺序的排序。

             XXX.frq保存了倒排表,也即包含每个词的文档ID列表。

             XXX.prx保存了倒排表中每个词在包含此词的文档中的位置。

    倒排

    倒排存储示例

    文章1的所有关键词为:[tom] [live] [guangzhou] [i] [live] [guangzhou]     文章2的所有关键词为:[he] [live] [shanghai]

    索引结构

    通常有两种位置:

    a.字符位置,即记录该词是文章中第几个字符(优点是关键词亮显时定位快);

    b.关键词位置,即记录该词是文章中第几个关键词(优点是节约索引空间、词组(phase)查询快),lucene中记录的就是这种位置。

    lucene将上面三列分别作为词典文件(Term Dictionary)、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词,还保留了指向频率文件和位置文件的指针,通过指针可以找到该关键字的频率信息和位置信息。

    倒排信息

    参考链接:Lucene索引过程中的内存管理与数据存储

     在Lucene的设计里,IntBlockPool和ByteBlockPool的作用域是IndexChain,即每个IndexChain都会生成独立的ByteBlockPool和IntBlockPool ,这样就不会出现多线程间可变数据共享的问题,这种做法实际上是一种约定方式的线程封闭,即ByteBlockPool本身并不是线程安全的,不像ThreadLocal或者栈封闭。由于每个IndexChain都需要处理多个Field,所以IntBlockPool和ByteBlockPool是Field所共享的。需要注意的是ParallelPostingsArray的作用域是Field,即每个Field都有一个postingsArray

      ParallelPostingsArray的三个成员变量:

       textStarts存储的是每一个term在ByteBlockPool里面的起始位置,通过textStarts[termID]可以快速找到termID对应的term 。

       byteStarts存储的是term在ByteBlockPool的结束位置的下一个位置。

       IntStarts存储的是term在IntBlockPool的地址信息,而IntBlockPool则存储着term在ByteBlockPool中的Slice位置信息。

    ParallelPostingsArray成员变量关系示例

    DOCID;Freq;Positions这三种信息都是随着Term存储在ByteBlockPool中,其存储过程如下:

         第一步:把term.length存储到ByteBlockPool.buffer中。这会占用1或者2个byte,由term的大小决定。由于term的最大长度为32766,所以term.length最多会占用两个byte。

        第二步:把term的byte数组形式存储到ByteBlockPool.buffer中。

        第三步:紧接着term开辟5个byte大小的slice,用来存储term在每个doc中的freq信息。

        第四步:再开辟一块Slice用来存储positions信息。

    Lucene存储在索引中的并非真正的docId,而是docDelta,即两个docId的差值.这样存储能够起到节约空间的作用。

    索引实现

    参考链接:Lucene底层实现原理,它的索引结构

    Lucene3.0之前使用的也是跳跃表结构,后换成了FST,但跳跃表在Lucene其他地方还有应用如倒排表合并和文档号索引。

    FST

    理论基础:《Direct constructionofminimal acyclic subsequential transducers》,通过输入有序字符串构建最小有向无环图。

    优点:内存占用率低,压缩率一般在3倍~20倍之间、模糊查询支持好、查询快

    缺点:结构复杂、输入要求有序、更新不易

    Lucene里有个FST的实现,从对外接口上看,它跟Map结构很相似,有查找,有迭代。

    与Map的性能对比

    倒排索引

    索引文件结构

    往索引库里插入四个单词abd、abe、acf、acg,看看它的索引文件内容如下:

    索引结构图

    构建过程如下:

    构建过程

    Lucene的FST实现的主要优化策略有:

    1. 最小后缀数。Lucene对写入tip的前缀有个最小后缀数要求,默认25,这时为了进一步减少内存使用。如果按照25的后缀数,那么就不存在ab、ac前缀,将只有一个跟节点,abd、abe、acf、acg将都作为后缀存在tim文件中。我们的10g的一个索引库,索引内存消耗只占20M左右。

    2.前缀计算基于byte,而不是char,这样可以减少后缀数,防止后缀数太多,影响性能。如对宇(e9 b8 a2)、守(e9 b8 a3)、安(e9 b8 a4)这三个汉字,FST构建出来,不是只有根节点,三个汉字为后缀,而是从unicode码出发,以e9、b8为前缀,a2、a3、a4为后缀。

    倒排表的docId压缩

    docId压缩存储

    跳跃表加速合并,因为布尔查询时,and 和or 操作都需要合并倒排表,这时就需要快速定位相同文档号,所以利用跳跃表来进行相同文档号查找。

    正排:

    正向信息在Lucene中只有docId-document的映射,由CompressingStoredFieldsWriter类来完成。

    Lucene的正向信息存储比较简单,按Field依次把内容写入到bufferedDocs中,然后把偏移量写入到endOffsets中就OK了。

    当满足flush条件或者执行了IndexWriter.commit()方法,则会进行一次flush操作,把内存中缓存的document及倒排信息flush到硬盘中。

    正向索引

    正向索引结构

    fnm中为元信息存放了各列类型、列名、存储方式等信息。

    段的元数据信息

    fdt为文档值,里面一个chunk就是一个块,Lucene索引文档时,先缓存文档,缓存大于16KB时,就会把文档压缩存储。一个chunk包含了该chunk起始文档、多少个文档、压缩后的文档内容。

    域数据文件

    fdx为文档号索引,倒排表存放的时文档号,通过fdx才能快速定位到文档位置即chunk位置,它的索引结构比较简单,就是跳跃表结构,首先它会把1024个chunk归为一个block,每个block记载了起始文档值,block就相当于一级跳表。

     

    域索引文件的作用示意

    所以查找文档,就分为三步:

        第一步二分查找block,定位属于哪个block。

        第二步就是根据从block里根据每个chunk的起始文档号,找到属于哪个chunk和chunk位置。

       第三步就是去加载fdt的chunk,找到文档。这里还有一个细节就是存放chunk起始文档值和chunk位置不是简单的数组,而是采用了平均值压缩法。所以第N个chunk的起始文档值由DocBase + AvgChunkDocs * n + DocBaseDeltas[n]恢复而来,而第N个chunk再fdt中的位置由StartPointerBase + AvgChunkSize * n + StartPointerDeltas[n]恢复而来。

         从上面分析可以看出,lucene对原始文件的存放是行式存储,并且为了提高空间利用率,是多文档一起压缩,因此取文档时需要读入和解压额外文档,因此取文档过程非常依赖随机IO,以及lucene虽然提供了取特定列,但从存储结构可以看出,并不会减少取文档时间。

    列式存储

    词向量(Term Vector)的数据信息

    词向量 信息是从索引(index)到文档(document)到域(field)到词(term)的正向信息,有了词向量信息,就可以得到一篇文档包含哪些词的信息。

    Lucene目前有五种类型的DocValues:NUMERIC、BINARY、SORTED、SORTED_SET、SORTED_NUMERIC,针对每种类型Lucene都有特定的压缩方法。

    如对NUMERIC类型即数字类型,数字类型压缩方法很多,如:增量、表压缩、最大公约数,根据数据特征选取不同压缩方法。

    SORTED类型即字符串类型,压缩方法就是表压缩:预先对字符串字典排序分配数字ID,存储时只需存储字符串映射表,和数字数组即可,而这数字数组又可以采用NUMERIC压缩方法再压缩。

    列式存储

    对DocValues的应用,ElasticSearch功能实现地更系统、更完整,即ElasticSearch的Aggregations——聚合功能,它的聚合功能分为三类: Metric -> 统计 、 Bucket ->分组 、 Pipline -> 基于聚合再聚合 。

    ElasticSearch基于倒排索引和DocValues实现SQL过程


    参考:

    Lucene原理与代码分析完整版

    https://www.iteye.com/blog/forfuture1978-691017

    展开全文
  • 1. 采用索引的动机 Heap file支持大规模顺序扫描数据.理论上来说,heap file的这个特性足以实现所有SQL中的查询操作。但是,实际上它的效率将会非常差。 在本篇文章中,我们讨论了一些简单的技巧,去提升数据扫描...

    原文地址:http://dblab.cs.toronto.edu/courses/443/2013/04.basic-index.html

    1. 采用索引的动机

    Heap file支持大规模顺序扫描数据.理论上来说,heap file的这个特性足以实现所有SQL中的查询操作。但是,实际上它的效率将会非常差。

    在本篇文章中,我们讨论了一些简单的技巧,去提升数据扫描(record scan)以及数据查找(record search)的效率。共同的主题将是:

    Create secondary data storage to minimize disk I/O for record scan and search.

    创建二级数据存储(磁盘),尽量减少数据扫描以及数据查找的磁盘I/O

    2. Sequential file

    Sequential fileheap file的一种,具有这些特性:

    a) page中的所有record都是按照某一个key进行排序的,具有如下的性质:

        ∀P, riP, ri[K]≤ri+1[K]

        其中:K是一个key,P表示heap file中的任意pageri表示P中的任意一条记录

    b) 对heap file中的任意page Pi Pi+1来说, Pi+1中的record关于Kvalue都比Pi :

        ∀Pi, rPi, rPi+1, rr

    因此可以说, Sequential filerecord按某个key K进行全排序的heap file.这样一来当我们查找某个record的时候,就可以根据key K进行二分查找.

    回顾heap file的设计:


    假如我们去寻找一条数据record r r[K]=v我们可以将directory page加载到内存,对其中page pointer指向的pages进行二分查找。总共需要的磁盘I/O的数目在最坏的情况下是:

        log2(Ndata pages)+(Ndirectory pages)

    sequential file并没有解决在顺序扫描时效率低下的问题。

    3. dense indexes(稠密索引或是全索引)

    dense indexes是通过对每一个record在磁盘上持久保存一些额外的数据,用于提高查询的效率。

    假设数据文件data file已经存在。

    K=(k1,k2,…,kn) 作为一个keydense index file是一个sequential file,它里面的记录是用K和指向data file中对应record的指针组成:

        rindex=(r[k1],r[k2],…,r[kn],address(r in Data File))

    dense index file中:


    dense index file的主要动机是:和data file中的record相比,dense index file能显著减少record的大小。因此,每一个index page能包含更多的record。对index file进行顺序扫描能显著的减少磁盘I/O,因为和data file相比我们从磁盘获取的page数目减少了。

    4. sparse index(稀疏索引)

    Sparse index结合sequential filedense index file的优点,通过保存部分key K作为它的record,能很好的支持二分查找快速查找record,并且能进一步减少所需的磁盘I/O

    想要利用sparse index filedata file必须是一个sequential file,也就是说data file中的record必须按K进行排序。

    Sparse index只保存key值和data file中每个page的第一条record的地址:

        (r[k1],r[k2],…,r[kn],address(P))



    这样就减少了sparse index中的index page的数目。在sparse index中查找record r[K]=v,我们需要这样:

    a)首先在sparse index中找到这样的一个record r

        r=argmaxrr[K]≤v

    可以利用二分查找(上面的公式表示要在sparse index找最接近v并且不大于v的那条记录)。

    b)在r所在的page中查找{r:r[K]=v}

        假设:为简单起见,我们只查找第一个满足条件的record

    5. multilevel sparse index: tree index(多极稀疏索引)

    Sparse index要求data file中的record必须是排好序的(比如sequential file),查询一条record需要:

        log2(Nindex pages)+1

    次磁盘I/O

    其中:log2(Nindex pages)是查询定位index page需要加载的page数目,1是表示需要加载1data page

    通过观察可以发现,其实sparse index也是一个sequential file,那么就使得更进一步提高性能成为可能。所以,我们可以给sparse index再加一个sparse index(这就是多级稀疏索引)。


    假设:Ddata fileI1是一级sparse indexI2是二级sparse indexND, NI1, NI2是对文件中的page数目。

    它们应该是这种关系:

    ND>NI1>NI2

    查找record需要的磁盘I/O开销是:

    log2(NI2)+2

    其中,log2(NI2)是在I2中定位需要加载的page数目,在I1中只需要加载一个page,在D中也是只需加载一个page

    6. indexed sequential access method(ISAM) 索引顺序访问方法

    6.1 Multilevel sparse index的局限性

    Multilevel sparse index能连续的应用。随着index level的增加,每层index page的数目会递减,直到最高层会只有一个index page


    伴随着Multilevel sparse index有很高的查询效率这个优点的同时,不幸的是它不能很好的支持recordinsert(插入)和update(修改)。回想一下,我们清楚的知道sparse index只能在有序的sequential file上加索引。因此,任何insertupdate操作必须维护record的有序性。Heap file也是仅支持有效率的append(追加)record,但是不支持record的有序性。

    6.2 ISAM

    ISAM虽然是一种基于Multilevel sparse index的索引技术,但是它克服了Multilevel sparse index存在的一些局限性。它支持快速的insertupdate

    ISAM的不同之处是,data file中的每一个data page都可以有任意数目的overflow page(溢出页)。当我们insert一个record r

    a)首先定位这样一个data page PiPi[0][K]r[K]<Pi+1[0][K]

    b)如果Pi中有空余空间,那么就将r insertPi

    c)如果Pioverflow page Q,并且Q有空余空间,那么就将r insertQ

    d)如果Pioverflow page全部都满了,那么就创建一个新的overflow page,将r insert进去。


            注:图中record(25, ...)就是我们刚insert进去的。当时在2030之间的那个page没有空余空间保存数据。因此,ISAM必须在那个page之后追加创建一个新的overflow page并链接之。可以这样说,record(25, ...)导致了新的overflow page的生成。

    6.3 ISAM的局限性

    ISAM放宽了record的有序性。于是就导致,获取record的最坏的性能是:

        log2(Nindex page)+max(Noverflow page)

    ISAM有着这种局限性的原因是:在record修改(包括updateinsert)的时候multilevel sparse index 一直是静态的。

    我们将讨论另外一种索引结构——B+tree,通过动态的调整树的平衡的方法来处理ISAM的性能退化。


    展开全文
  • 索引是什么?...但是有了索引之后,只需要在索引里面去检索这条数据就行了,因为它是一种特殊的专门用来快速检索的数据结构,我们找到数据存放的磁盘地址以后,就可以拿到数据了。 就像我们从一本50

    索引是什么?

    索引是帮助 MySQL 高效获取数据的排好序数据结构

    第一个问题,为什么说索引能高效获取数据呢?

    在这里插入图片描述

    首先数据是以文件的形式存放在磁盘上面的,每一行数据都有它的磁盘地址。如果没有索引的话,要从500万行数据里面检索一条数据,只能依次遍历这张表的全部数据,直到找到这条数据。

    但是有了索引之后,只需要在索引里面去检索这条数据就行了,因为它是一种特殊的专门用来快速检索的数据结构,我们找到数据存放的磁盘地址以后,就可以拿到数据了。

    就像我们从一本 500 页的书里面去找特定的一小节的内容,肯定不可能从第一页开始翻。那么这本书有专门的目录,它可能只有几页的内容,它是按页码来组织的,可以根据拼音或者偏旁部首来查找,只要确定内容对应的页码,就能很快地找到我们想要的内容。

    索引都有什么类型?在InnoDB 里面,索引类型有三种,普通索引、唯一索引(主键索引是特殊的唯一索引)、全文索引。

    • 普通(Normal):也叫非唯一索引,是最普通的索引,没有任何的限制。
    • 唯一(Unique):唯一索引要求键值不能重复。另外需要注意的是,主键索引是一种特殊的唯一索引,它还多了一个限制条件,要求键值不能为空。主键索引用primaykey创建。
    • 全文(Fulltext):针对比较大的数据,比如我们存放的是消息内容,有几KB的数据的这种情况,如果要解决like查询效率低的问题,可以创建全文索引。只有文本类型的字段才可以创建全文索引,比如char、varchar、text。

    明白了第一个问题,那还剩下一个问题。我们说索引是一种数据结构,那么它到底应该选择一种什么数据结构,才能实现数据的高效检索呢,并且将所有数据排好序呢?我们就带着问题向下看…


    1.数组/链表

    双十一过去之后,你女朋友跟你玩了一个猜数字的游戏。猜猜我昨天买了多少钱,给你五次机会。


    10000?低了。30000?高了。接下来你会猜多少?
    20000。为什么你不猜11000,也不猜29000呢?

    其实这个就是二分查找的一种思想,也叫折半查找,每一次,我们都把候选数据缩小了一半。如果数据已经排过序的话,这种方式效率比较高。

    所以第一个,我们可以考虑用有序数组作为索引的数据结构。有序数组的等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题,可能要挪动大量的数据(改变index),所以只适合存储静态的数据。

    为了支持频繁的修改,比如插入数据,我们需要采用链表。链表的话,如果是单链表,它的查找效率还是不够高。所以,有没有可以使用二分查找的链表呢?为了解决这个问题,BST(Binary SearchTree)也就是我们所说的二叉查找树诞生了。

    2.二叉查找树(BST Binary Search Tree)

    二叉查找树的特点是什么?左子树所有的节点都小于父节点,右子树所有的节点都大于父节点。投影到平面以后,就是一个有序的线性表。

    在这里插入图片描述

    二叉查找树既能够实现快速查找,又能够实现快速插入。但是二叉查找树有一个问题:就是它的查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成O(n)。比如,我们插入的数据刚好是有序的,比如 [2、6、11、13、17、22] 这个时候我们的二叉查找树变成了什么样了呢?

    它会变成链表(我们把这种树叫做“斜树”),这种情况下不能达到加快检索速度的目的,和顺序查找效率是没有区别的。

    造成它倾斜的原因是什么呢?因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。

    所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢?这个就是平衡二叉树,叫做Balanced binary search trees,或者AVL树(AVL 是发明这个数据结构的人的名字)。

    3.平衡二叉树(AVL Tree)(左旋、右旋)

    平衡二叉树的定义:左右子树深度差绝对值不能超过1。

    是什么意思呢?比如左子树的深度是2,右子树的深度只能是1或者3。这个时候我们再按顺序插入1、2、3、4、5、6,一定是这样,不会变成一棵“斜树” 。

    在这里插入图片描述

    那它的平衡是怎么做到的呢?怎么保证左右子树的深度差不能超过1呢? 拿插入1、2、3 来说吧,当我们插入了1、2 之后,如果按照二叉查找树的定义,3 肯定是要在 2 的右边的,这个时候根节点1的右节点深度会变成 2,但是左节点的深度是 0,因为它没有子节点,所以就会违反平衡二叉树的定义。那应该怎么办呢?

    因为它是右节点下面接一个右节点,右-右型,所以这个时候我们要把2提上去,这个操作叫做左旋。

    在这里插入图片描述

    同样的,如果我们插入7、6、5,这个时候会变成左左型,就会发生右旋操作,把 6 提上去。

    在这里插入图片描述

    所以为了保持平衡,AVL树在插入和更新数据的时候执行了一系列的计算和调整的操作。

    索引应该存储什么内容?

    平衡的问题我们解决了,那么平衡二叉树作为索引怎么查询数据?在平衡二叉树中,一个节点,它的大小是一个固定的单位,作为索引应该存储什么内容?它应该存储三块的内容:

    • 第一个是索引的键值。比如我们在id上面创建了一个索引,我在用 where id=1 的条件查询的时候就会找到索引里面的id的这个键值。
    • 第二个是数据的磁盘地址,因为索引的作用就是去查找数据的存放的地址。
    • 第三个,因为是二叉树,它必须还要有左子节点和右子节点的引用,这样我们才能找到下一个节点。比如大于26的时候,走右边,到下一个树的节点,继续判断。

    在这里插入图片描述

    如果是这样存储数据的话,会存在什么问题?

    首先,索引的数据,是放在硬盘上的。当我们用树的结构来存储索引的时候,访问一个节点就要跟磁盘之间发生一次IO。InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是16K(16384字节)。那么,一个树的节点就是16K的大小。如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到16K的容量,所以访问一个树节点,进行一次IO的时候,浪费了大量的空间。

    所以如果每个节点存储的数据太少,从索引中找到我们需要的数据,就要访问更多的节点,意味着跟磁盘交互次数就会过多。如果是机械硬盘时代,每次从磁盘读取数据需要10ms左右的寻址时间,交互次数越多,消耗的时间就越多。

    比如上面这张图,我们一张表里面有6条数据,当我们查询id=37的时候,要查询两个子节点,就需要跟磁盘交互3 次,如果我们有几百万的数据呢?这个时间更加难以估计。

    所以,解决方案是什么呢?

    可以从下面两点去优化:

    • 第一,让每个节点存储更多的数据。
    • 第二,节点上的关键字的数量越多,我们的指针数也越多,也就是意味着可以有更多的分叉(我们把它叫做“路数”)。因为分叉数越多,树的深度就会减少(根节点是0)。这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子?这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。

    4.多路平衡查找树(B Tree)(分裂、合并)

    Balanced Tree,这个就是我们的多路平衡查找树,叫做B Tree(B代表平衡)。跟AVL树一样,B树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点:分叉数(路数)永远比关键字数多1。比如我们画的这棵树,每个节点存储两个关键字(索引数据),那么就会有三个指针指向三个子节点。

    在这里插入图片描述

    B Tree的查找规则是什么样的呢?比如我们要在这张表里面查找15。

    1. 因为15小于17,走左边。
    2. 因为15大于12,走右边。

    在磁盘块7里面就找到了15,只用了3次IO。


    这个是不是比AVL 树效率更高呢?那BTree又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟AVL树有什么区别? 比如MaxDegree(路数)是3的时候,我们插入数据1、2、3,在插入3的时候,本来应该在第一个磁盘块,但是如果一个节点有三个关键字的时候,意味着有 4个指针,子节点会变成 4 路,所以这个时候必须进行分裂。把中间的数据2提上去,把1和3变成2的子节点。

    在这里插入图片描述

    如果删除节点,会有相反的合并的操作。注意这里是分裂和合并,跟AVL树的左旋和右旋是不一样的。我们继续插入4和5,B Tree又会出现分裂和合并的操作。

    节点的分裂和合并,其实就是InnoDB页的分裂和合并。

    5.B+树(加强版多路平衡查找树)

    B Tree 的效率已经很高了,为什么 MySQL 还要对 B Tree 进行改良,最终使用了B+Tree呢?总体上来说,这个B树的改良版本解决的问题比B Tree更全面。我们来看一下InnoDB里面的B+树的存储结构:

    在这里插入图片描述

    MySQL中的B+Tree有几个特点:

    1. 它的关键字的数量是跟路数相等的;

    2. B+Tree 的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。搜索到关键字不会直接返回,会到最后一层的叶子节点。

      • 比如我们搜索 id=28,虽然在第一层直接命中了,但是全部的数据在叶子节点上面,所以我还要继续往下搜索,一直到叶子节点。
      • 假设一条记录是1K,一个叶子节点(一页)可以存储16条记录。非叶子节点可以存储多少个指针?
        假设索引字段是bigint 类型,长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节,这样一共 14 字节。非叶子节点(一页)可以存储16384/14=1170个这样的单元(键值+指针),代表有1170个指针。树深度为 2 的时候 , 有 1170 ^2 个 叶子节点 , 可以存储的数据为 1170*1170*16=21902400

      在这里插入图片描述

      在查找数据时一次页的查找代表一次 IO,也就是说,一张2000万左右的表,查询数据最多需要访问3次磁盘。所以在 InnoDB 中 B+ 树深度一般为 1-3 层,它就能满足千万级的数据存储。

    3. B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

    4. 它是根据左闭右开的区间 [ )来检索数据。我们来看一下B+Tree的数据搜寻过程:

      1. 比如我们要查找 28,在根节点就找到了键值,但是因为它不是页子节点,所以会继续往下搜寻,28是[28,66)的左闭右开的区间的临界值,所以会走中间的子节点,然后继续搜索,它又是[28,34)的左闭右开的区间的临界值,所以会走左边的子节点,最后在叶子节点上找到了需要的数据。
      2. 如果是范围查询,比如要查询从22到60的数据,当找到22之后,只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点,这样就极大地提高了区间查询效率(不需要返回上层父节点重复遍历查找)。

    总结一下,InnoDB中的B+Tree的特点:

    1. 它是BTree的变种,BTree能解决的问题,它都能解决。BTree解决的两大问题是什么?(每个节点存储更多关键字;路数更多)
    2. 扫库、扫表能力更强(如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵B+Tree拿到所有的数据)
    3. B+Tree的磁盘读写能力相对于BTree来说更强(根节点和枝节点不保存数据区,所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多)
    4. 排序能力更强(因为叶子节点上有下一个数据区的指针,数据形成了链表)
    5. 效率更加稳定(B+Tree永远是在叶子节点拿到数据,所以IO次数是稳定的)

    6.为什么不用红黑树?

    红黑树也是BST树,但是不是严格平衡的。必须满足5个约束:

    1. 节点分为红色或者黑色。
    2. 根节点必须是黑色的。
    3. 叶子节点都是黑色的NULL节点。
    4. 红色节点的两个子节点都是黑色(不允许两个相邻的红色节点)。
    5. 从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点。

    比如插入:60、56、68、45、64、58、72、43、49

    在这里插入图片描述

    基于以上规则,可以推导出:从根节点到叶子节点的最长路径(红黑相间的路径)不大于最短路径(全部是黑色
    节点)的2倍。

    为什么不用红黑树?1、只有两路;2、不够平衡。红黑树一般只放在内存里面用。例如Java的TreeMap。

    7.哈希表也能作为索引?

    在Navicat的工具中,创建索引,索引方式有两种,Hash和BTree。BTree上面说了,而Hash是以KV的形式检索数据,也就是说,它会根据索引字段生成哈希码和指针,指针指向数据。

    在这里插入图片描述

    哈希索引有什么特点呢?

    1. 它的时间复杂度是O(1),查询速度比较快。因为哈希索引里面的数据不是按顺序存储的,所以不能用于排序。
    2. 我们在查询数据的时候要根据键值计算哈希码,所以它只能支持等值查询(= IN),不支持范围查询(> < >= <= between and)。
    3. 如果字段重复值很多的时候,会出现大量的哈希冲突(采用拉链法解决),效率会降低。

    InnoDB可以在客户端创建一个索引,使用哈希索引吗?

    InnoDB 只支持显式创建 B+Tree 索引,对于一些热点数据页,InnoDB会自动建立自适应Hash索引,也就是在B+Tree索引基础上建立Hash索引,这个过程对于客户端是不可控制的,隐式的。

    我们在Navicat工具里面选择索引方法是哈希,但是它创建的还是B+Tree索引,这个不是我们可以手动控制的。上篇我们说到 buffer pool里面有一块区域是 Adaptive Hash Index 自适应哈希索引,就是这个。

    这个开关默认是ON:

    show variables like 'innodb_adaptive_hash_index';
    

    在这里插入图片描述

    最后,因为BTree和B+Tree的特性,它们广泛地用在文件系统和数据库中,例如Windows的HPFS文件系统,Oracel、MySQL、SQLServer数据库。

    展开全文
  • 上一篇,我们介绍了MySQL为什么最终选择了B+树来作为索引存储的数据结构,想要详细了解,请点击这里。本文将为大家介绍一下B+树在MySQL中是如何落地的,本文主要会对比常用的两种存储引擎InnoDB和MyISAM来进行比较...
  • 索引结构

    2017-12-21 18:58:06
    传统的索引 顺序文件是对关系中的元组按主键进行排序...一般查找键与指针所占的存储空间远小于记录本身,这样一个块中能存储比较多的索引块,从访问磁盘的特性理解也就是查找索引里面的指针会更快,从而更快定位记录。
  • 索引结构和散列结构适用在外存与内存交互结构。顺序存储在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。特点:随机存取表中元素。插入和删除操作需要移动元素。链接...
  • Mysql原理解析 - 索引文件的存储结构

    万次阅读 2021-02-10 00:54:40
    mysql索引数据结构 -- B+树 前言 局部性原理 磁盘预读 磁盘预读(预读的长度一般为页(page)的整数倍) – 页是存储器的逻辑块,操作系统往往将主存和磁盘存储区分割为连续的大小 相等的块,每个存储块称为一页...
  • ClickHouse存储结构索引详解

    千次阅读 2021-01-15 11:10:08
    本文基于ClickHouse 20.8.5.45版本编写,操作系统使用的是CentOS 7.5,主要介绍MergeTree表引擎的存储结构以及索引过程,希望通过本文能够让大家对ClickHouse的底层有个更详细的了解。 创建表 创建语句 ...
  • 1 mysql中的逻辑存储结构 2 数据结构 2.1 二分查找 2.2 二叉排序树 2.3 平衡二叉树 2.4 B树和B+树 3 B树索引 1 mysql中的逻辑存储结构 1 表空间 基于InnoDB存储引擎的mysql数据库,存放在数据库中的数据...
  • ES索引结构存储原理

    万次阅读 2019-08-19 14:57:17
    ES索引结构存储原理 ES(ElasticSearch)是一款分布式全文检索框架,底层基于基于Lucene实现。 ES索引存储原理 不变性 写到磁盘的倒序索引是不变的:自从写到磁盘就再也不变。 这会有很多好处: 不需要添加锁...
  • 文章目录一、索引相关面试题说下索引底层...InnoDB的表数据文件,本身就是一个索引结构的文件,必须需要主键,mySQL会给InnoDB的表自动生成一个主键,他的数据文件按照索引结构存储。 InnoDB表主键为什么推荐使用自增的
  • MySQL索引结构

    千次阅读 2019-02-23 10:31:49
    文章目录常见索引类型Hash索引B+索引InnoDB的索引结构主键索引和普通索引的区别索引维护主键ID自增覆盖索引联合索引索引下推 数据库的索引就像一本书的目录一样,它可以快速定位你所需要的信息。下面来详细说一下...
  • 索引存储引擎快速找到记录的一种数据结构,是数据库中专门用于帮助用户快速查询数据的一种数据结构,可以帮助用户快速寻找到需要的数据行,是数据库性能优化中最重要的工具。 使用索引的主要目的是为了优化查询...
  • 联合索引
  • HBase 索引结构

    千次阅读 2017-12-26 14:08:20
    1. 索引表的结构在HBase中,表格的Rowkey按照字典排序,Region按照RowKey设置split point进行shard,通过这种方式实现的全局、分布式索引,成为了其成功的最大的砝码每一个索引建立一个表,然后依靠表的row key来...
  • MySQL索引存储问题

    2020-08-04 10:30:07
    MySQL索引存储问题 1 索引简述 MySQL中的索引结构 在MySQL中,使用最多的索引结构是B+树索引,此外还有哈希索引,但很少使用。 哈希表原则上查找更快,但基本不使用,因为哈希表解决不了范围查找,只能等值查询...
  • 静态索引结构

    2014-11-13 11:12:17
    索引结构   来源:http://blogold.chinaunix.net/u2/61062/showart_2035566.html     索引结构和散列结构是用在外部搜索的搜索结构。 数据在外存中的组织的方式也就是文件结构,主要分成顺序、直接存取...
  • 【进阶】索引底层数据结构和算法

    千次阅读 2019-03-14 13:23:38
    前言 文章基于MySql 5.7.24分析,部分图片源于网络,是MySql索引学习笔记。 MySQL数据库支持多种索引类型,如BTree索引,哈希...索引存储在文件里面索引就好比书的目录,你可以通过目录直接找到对应的目标,...
  • MySQL索引数据结构

    2021-05-19 00:01:26
    索引是帮助Mysql高效获取数据的排好序的数据结构 索引的数据结构 二叉树 红黑树 Hash表 B-Tree select * from t where t.col2=89; 例如查找89,如果没有索引需要进行全表扫描,需要至少进行6次扫描。 如果使用...
  • 索引的数据结构主要有以下几种: (1)生成索引,建立二叉查找树/二叉排序树/二叉搜索树进行二分查找; (2)平衡二叉树,红黑树; (3)生成索引,建立B-Tree(B树/B-树)结构进行查找; (4)生成索引,建立B±Tree...
  • Mysql索引底层数据结构与算法

    千次阅读 2018-10-10 17:25:44
    2,索引底层数据结构与算法 3,索引最左前缀原理   索引到底是什么 •索引是帮助MySQL高效获取数据的排好序的数据结构 索引的本质 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构...
  • 这些技术中的每一种技术都使用不同的存储机制、索引技巧、锁定水平并且最终提供广泛的不同的功能和能力。通过选择不同的技术,你能够获得额外的速度或者功能,从而改善你的应用的整体功能。 这些不同的技术以及配套...
  • 【mysql知识点整理】 --- mysql索引底层数据结构

    千次阅读 多人点赞 2020-02-28 12:34:47
    文章目录1 什么是索引 1 什么是索引 索引是帮助MySQL高效的获取数据的数据结构
  • MySQL索引的数据结构以及算法原理

    万次阅读 多人点赞 2018-04-19 22:13:28
    写在前面的话 在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法),但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性,...
  • 首先,需要了解的是Mysql的Innodb存储结构是一颗B+树。 B+树的结构如下图: 可以看出,B+树和二叉树的区别: (1)一个节点里面可以存取多个元素 (2)叶子节点和叶子节点之间有指针; (3)所有非叶子节点在叶子...
  • 串是一种特殊的线性表,所以先得搞清楚线性表的顺序、链式存储,在其基础上便可以清楚分析特殊线性表的存储结构:栈、队列、串 顺序:结构体里面定义一个数组+长度等辅助信息 链式:结构体里面定义一个元素数据类型+...
  • 索引的知识以mysql为基本,虽然本人项目使用的PGSql....B,B+树的性能考量:我们知道数据库的文件都是存储在磁盘中,那么IO操作就是评价一个索引结构好坏的最好标准。如果这个索引是顺序结构,那么查询一个数据的时间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 185,415
精华内容 74,166
关键字:

索引里面的存储的结构