精华内容
下载资源
问答
  • 索引存储
    千次阅读
    2020-09-09 07:43:59

    存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。

    顺序结构和链接结构适用在内存结构中。 顺序表每个单元都是按物理顺序排列的,如果你想访问那个单元你可以根据提供的指针等直接访问到需要的东西,但是链表是逻辑连续不是物理连续,你要访问必须从第一个指针一个一个往下找,直到找到位置

    索引结构和散列结构适用在外存与内存交互结构。

    顺序存储:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

    特点:

    1、随机存取表中元素。

    2、插入和删除操作需要移动元素。

    链接存储:在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

    特点:

    1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
    2、逻辑上相邻的节点物理上不必相邻。
    3、插入、删除灵活 (不必移动节点,只要改变节点中的指针)。
    4、查找结点时链式存储要比顺序存储慢。
    5、每个结点是由数据域和指针域组成。

    索引存储:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

    特点:

    索引存储结构是用结点的索引号来确定结点存储地址,其优点是检索速度快,缺点是增加了附加的索引表,会占用较多的存储空间。

    散列存储:散列存储,又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

    散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外,还可以用于存储。

    特点:

    散列是数组存储方式的一种发展,相比数组,散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数据在数组中的存储位置,进而能够快速实现数据的访问,理想的散列访问速度是非常迅速的,而不像在数组中的遍历过程,采用存储数组中内容的部分元素作为映射函数的输入,映射函数的输出就是存储数据的位置,这样的访问速度就省去了遍历数组的实现,因此时间复杂度可以认为为O(1),而数组遍历的时间复杂度为O(n)

    更多相关内容
  • 索引存储结构

    千次阅读 2019-07-26 20:13:23
    四种数据存储结构---顺序存储 链接存储 索引存储 散列存储 转自:https://www.cnblogs.com/fengty90/p/3768826.html 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存...

    四种数据存储结构---顺序存储 链接存储 索引存储 散列存储

    转自:https://www.cnblogs.com/fengty90/p/3768826.html

    存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储

    顺序结构和链接结构适用在内存结构中。

    索引结构和散列结构适用在外存与内存交互结构。

     

    顺序存储:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

    特点:

    1、随机存取表中元素。

    2、插入和删除操作需要移动元素。

     

    链接存储:在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

    特点:

    1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
    2、逻辑上相邻的节点物理上不必相邻。
    3、插入、删除灵活 (不必移动节点,只要改变节点中的指针)。
    4、查找结点时链式存储要比顺序存储慢。
    5、每个结点是由数据域和指针域组成。

     

    索引存储:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

    特点:

    索引存储结构是用结点的索引号来确定结点存储地址,其优点是检索速度快,缺点是增加了附加的索引表,会占用较多的存储空间。

     

    散列存储:散列存储,又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

    散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外,还可以用于存储。

    特点:

    散列是数组存储方式的一种发展,相比数组,散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数据在数组中的存储位置,进而能够快速实现数据的访问,理想的散列访问速度是非常迅速的,而不像在数组中的遍历过程,采用存储数组中内容的部分元素作为映射函数的输入,映射函数的输出就是存储数据的位置,这样的访问速度就省去了遍历数组的实现,因此时间复杂度可以认为为O(1),而数组遍历的时间复杂度为O(n)。

    展开全文
  • 首先看看课本的索引存储结构的解析 索引表里必须存关键字这一项,这就出现很大的冗余 但是散列存储(哈希存储)的区别特殊性:体现在它的关键码能确定数据元素的存储位置;还可以用来制作缓存,在没有redis等缓存...

    首先看看课本的索引存储结构的解析
    索引表里必须存关键字这一项,这就出现很大的冗余
    在这里插入图片描述

    但是散列存储(哈希存储)的区别特殊性:体现在它的关键码能确定数据元素的存储位置;还可以用来制作缓存,在没有redis等缓存手段的时代使用哈希存储结构来制作缓存的

    看一条题目:
    在这里插入图片描述

    在这里插入图片描述
    上图用一个数组来存储关键字,这数组里面的关键字都是通过一个散列函数来确定的

    索引存储:
    除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

    特点:

    索引存储结构是用结点的索引号来确定结点存储地址,其优点是检索速度快,缺点是增加了附加的索引表,会占用较多的存储空间。

    散列存储:
    散列存储,又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

    散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外,还可以用于存储。

    其实没必要咬文嚼字。哈希也可以用来制作索引。完成索引的功能。。。
    mysql的索引表使用B+树来制作的

    展开全文
  • MySQL索引篇之索引存储模型

    千次阅读 2020-11-07 19:36:30
      上篇文章我们介绍了什么是索引索引的类型,明白了索引其实也是通过特定的数据结构来存储的数据,作用是用来提升我们查询和更新数据的效率的,本文我们就来推演下索引存储模型 二分查找   给定一个1~100的...

      上篇文章我们介绍了什么是索引和索引的类型,明白了索引其实也是通过特定的数据结构来存储的数据,作用是用来提升我们查询和更新数据的效率的,本文我们就来推演下索引的存储模型

    二分查找

      给定一个1~100的自然数,给你5次机会,你能猜中这个数字吗?
    你会从多少开始猜?
      为什么一定是50呢?这个就是二分查找的一种思想,也叫折半查找,每一次,我们都把候选数据缩小了一半。如果数据已经排过序的话,这种方式效率比较高。
      所以第一个,既然索引是有序的,我们可以考虑用有序数组作为索引的数据结构。
      有序数组的等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题,可能要挪动大量的数据(改变index),所以只适合存储静态的数据。
      为了支持频繁的修改,比如插入数据,我们需要采用链表。链表的话,如果是单链表,它的查找效率还是不够高。
      所以,有没有可以使用二分查找的链表呢?
      为了解决这个问题,BST(Binary [ˈbaɪnəri] Search Tree)也就是我们所说的二叉查找树诞生了。

    二叉查找树

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

    在这里插入图片描述
      二叉查找树既能够实现快速查找,又能够实现快速插入。
      但是二叉查找树有一个问题:查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成O(n)。
      什么情况是最坏的情况呢?
    https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
      还是刚才的这一批数字,如果我们插入的数据刚好是有序的,2、6、11、13、17、22。
      这个时候BST会变成链表( “斜树”),这种情况下不能达到加快检索速度的目的,和顺序查找效率是没有区别的。

    在这里插入图片描述
      造成它倾斜的原因是什么呢?
      因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。
      所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢?
      这个就是平衡二叉树,叫做Balanced binary search trees,或者AVL树(AVL是发明这个数据结构的人的名字)。

    平衡二叉树

      AVL Trees (Balanced binary search trees)
      平衡二叉树的定义:左右子树深度差绝对值不能超过1。
      是什么意思呢?比如左子树的深度是2,右子树的深度只能是1或者3。
      这个时候我们再按顺序插入1、2、3、4、5、6,一定是这样,不会变成一棵“斜树”。
    在这里插入图片描述

      那AVL树的平衡是怎么做到的呢?怎么保证左右子树的深度差不能超过1呢?
      https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
      插入1、2、3。
      当我们插入了1、2之后,如果按照二叉查找树的定义,3肯定是要在2的右边的,这个时候根节点1的右节点深度会变成2,但是左节点的深度是0,因为它没有子节点,所以就会违反平衡二叉树的定义。
      那应该怎么办呢?因为它是右节点下面接一个右节点,右-右型,所以这个时候我们要把2提上去,这个操作叫做左旋。

    在这里插入图片描述

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

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

      平衡的问题我们解决了,那么平衡二叉树作为索引怎么查询数据?
      在平衡二叉树中,一个节点,它的大小是一个固定的单位,作为索引应该存储什么内容?
      它应该存储三块的内容:
      第一个是索引的键值。比如我们在id上面创建了一个索引,我在用where id =1的条件查询的时候就会找到索引里面的id的这个键值。
      第二个是数据的磁盘地址,因为索引的作用就是去查找数据的存放的地址。
      第三个,因为是二叉树,它必须还要有左子节点和右子节点的引用,这样我们才能找到下一个节点。比如大于26的时候,走右边,到下一个树的节点,继续判断。

    在这里插入图片描述
      当我们用树的结构来存储索引的时候,因为拿到一块数据就要在Server层比较是不是需要的数据,如果不是的话就要决定走左子树还是右子树,再读一一个节点。访问一个树的节点就是一次磁盘的I/O操作。
      因为InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块),page的默认大小是16KB(16384字节)。那么,读取一个树的节点就是读取16KB的大小。
    如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到16384个字节的容量。所以访问一个树节点,进行一次I/O的时候,浪费了大量的空间。
      所以如果每个节点存储的数据太少,从索引中找到我们需要的数据,就要访问更多的节点,意味着跟磁盘交互次数就会过多。
      如果是机械硬盘时代,每次从磁盘读取数据需要10ms左右的寻址时间,交互次数越多,消耗的时间就越多。

    在这里插入图片描述
      比如上面这张图,我们一张表里面有6条数据,当我们查询id=37的时候,要查询两个子节点,就需要跟磁盘交互3次,如果我们有几百万的数据呢?这个时间更加难以估计。
      所以我们的解决方案是什么呢?
      第一个就是让每个节点存储更多的数据,充分利用16KB的大小,这样读取一个节点就能对比更多数据,较少对比次数。
      第二个,节点上的关键字的数量越多,我们的指针数也越多,也就是意味着可以有更多的分叉(我们把它叫做“路数”)。
      因为分叉数越多,树的深度就会减少(根节点是0)。
      这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子?
      这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。

    多路平衡查找树

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

    在这里插入图片描述
      B Tree的查找规则是什么样的呢?
      比如我们要在这张表里面查找15。
      因为15小于17,走左边。
      因为15大于12,走右边。
      在磁盘块7里面就找到了15,只用了3次IO。

      这个是不是比AVL 树效率更高呢?
      那B Tree又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟AVL树有什么区别?
    https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
      比如Max Degree(路数)是3的时候,我们插入数据1、2、3,在插入3的时候,本来应该在第一个磁盘块,但是如果一个节点有三个关键字的时候,意味着有4个指针,子节点会变成4路,所以这个时候必须进行分裂(其实就是B+Tree)。把中间的数据2提上去,把1和3变成2的子节点。
      如果删除节点,会有相反的合并的操作。
      注意这里是分裂和合并,跟AVL树的左旋和右旋是不一样的。
      我们继续插入4和5,B Tree又会出现分裂和合并的操作。

    在这里插入图片描述
      从这个里面我们也能看到,在更新索引的时候会有大量的索引的结构的调整,所以解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。
      节点的分裂和合并,其实就是InnoDB页(page)的分裂和合并。

    B+树

      加强版多路平衡查找树
      因为B Tree的这种特性非常适合用于做索引的数据结构,所以很多文件系统和数据库的索引都是基于B Tree的。
      但是实际上,MySQL里面使用的是B Tree的改良版本,叫做B+Tree(加强版多路平衡查找树)。

    B+树的存储结构:
    在这里插入图片描述

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

    1. 它的关键字的数量是跟路数相等的;
    2. B+Tree的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。InnoDB 中 B+ 树深度一般为 1-3 层,它就能满足千万级的数据存储。搜索到关键字不会直接返回,会到最后一层的叶子节点。比如我们搜索id=28,虽然在第一层直接命中了,但是全部的数据在叶子节点上面,所以我还要继续往下搜索,一直到叶子节点。
    3. B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

    在这里插入图片描述

    总结一下, B+Tree的特点带来的优势:

    1. 它是B Tree的变种,B Tree能解决的问题,它都能解决。B Tree解决的两大问题是什么?(每个节点存储更多关键字;路数更多)
    2. 扫库、扫表能力更强(如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵B+Tree拿到所有的数据)
    3. B+Tree的磁盘读写能力相对于B Tree来说更强(根节点和枝节点不保存数据区,所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多)
    4. 排序能力更强(因为叶子节点上有下一个数据区的指针,数据形成了链表)
    5. 效率更加稳定(B+Tree永远是在叶子节点拿到数据,所以IO次数是稳定的)
    展开全文
  • 索引是定义在存储表(Table)基础之上,有助于无需检查所有记录而快速定位所需记录的一种辅助存储结构,由一系列存储在磁盘上的索引项(indexentries)组成,每一索引项又由两部分构成: 索引字段:由Table中某些列...
  • MySQL——索引存储在磁盘上

    千次阅读 2021-02-07 11:06:24
    通常,索引本身很大,不能完全存储在内存中,因此索引通常作为索引文件存储在磁盘上。在这种情况下,在索引查找过程中会生成磁盘I/O...MySQL——索引存储在磁盘上磁盘由相同大小和同轴的圆盘组成,磁盘可以旋转(每...
  • MySQL索引详解之索引存储方式

    千次阅读 2020-04-21 18:53:46
    前言 很多人对数据库索引可能都是知其然却不知其所以然,对索引没有很深入的理解,在使用...索引存储方式 索引的利弊以及高效使用 数据存储方式 上篇文章我们了解了索引的数据结构,下面我们再来了解另外一个概念...
  • 我们mysql底层的索引存储数据结构是按照B+树方式来存储的,也是从B树结构演变而来。 我们知道索引就是类似我们的书本的目录页,存储要找的内容所在的页数。 B树的结构: 叶节点具有相同的深度,叶节点的指针为空 ...
  • 【mysql】mysql索引存储结构和特点

    万次阅读 多人点赞 2019-08-22 09:14:40
    MySQL索引存储结构和特点 一 理解索引的特性 二 索引的各种存储结构及其优缺点 (一)二叉树 ​(二)红黑树 (三)Hash (四)B-Tree (五) B+Tree(MySQL索引的真正存储结构) 三. 联合索引底层存储结构 ...
  • 数据库索引存储结构

    千次阅读 2018-11-08 17:16:08
    数据库索引存储结构 主键索引(PRIMAY KEY):  一个表中只能有一个主键,创建主键自动创建主键索引,该索引是唯一索引,其主键列的数据值不重复。建议使用INT型的自动增长主键,这样索引效率最高。 ...
  • MySQL索引存储结构(5种)

    千次阅读 2019-10-10 13:22:28
    MySQL数据库索引存储结构一般有以下几种。 二叉树 红黑树 HASH B-Tree B+Tree(现在常用) 首先我们要了解的是:索引文件是存储在磁盘中的,cpu到磁盘拿取数据一般经过两步:寻道时间(磁头左右移动,速度慢,...
  • 但是索引的方式相当于给一个本书加一个目录,这样子就可以快速找到每一个章节。好处就是增加检索速度,坏处就是增加了书的厚度,而且如果改变了书的内容,目录也要动态更新。 散列(哈希)可以不是连续地存储,它...
  • ES索引存储原理

    万次阅读 多人点赞 2017-08-06 14:36:54
    ES索引存储原理不变性写到磁盘的倒序索引是不变的:自从写到磁盘就再也不变。 这会有很多好处: 不需要添加锁。不存在写操作,因此不存在多线程更改数据。 提高读性能。一旦索引被内核的文件系统做了Cache,绝大...
  • es 索引存储 .md

    2019-04-24 13:17:45
    首先介绍几个es中支持的索引存储方式: 1.simplefs: 简单的粗盘存放, 这种方式会有大量的磁盘IO,因此索引的建立和索引非常依赖磁盘的性能; 2.niofs: 使用 NIO 方式读写索引;NIO 是 java New IO 的简称,NIO ...
  • MYSQL的索引存储引擎

    多人点赞 热门讨论 2022-05-17 12:03:50
    MYSQL的索引存储引擎 介绍 索引是通过某种算法,构建出一个数据模型,用于快速查出在某个列中有一特定值的行,不使用索引,MYSQL必须从第一行记录开始读完整个表,直到找出相关的行,表越大,查询数据所花费的时间就越多,...
  • Elasticsearch是一个建立在全文搜索引擎库Apache Lucene 基础上的分布式搜索引擎,Lucene最早的版本是2000年发布的,距今...Index:索引,由很多的Document组成。 Document:由很多的Field组成,是Index和Search的...
  • 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存结构中。 索引结构和散列结构适用在外存与内存交互结构。 顺序存储:在计算机中用一组地址连续的存储单元依次存储...
  • myisam与innodb索引与数据存储 一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ,而且到任何一个 Leaf Node ...
  • ** MYSQL InnoDB二级索引存储主键值而不是存储行指针的优点与缺点** 优点 减少了出现行移动或者数据页分裂时二级索引的维护工作(当数据需要更新的时候,二级索引不需要修改,只需要修改聚簇索引,一个表只能有一个...
  • Mysql中的索引存储

    2021-01-31 04:08:48
    索引的使用与数据库中表的引擎有一定的关联索引存储的数据类型分为两种:BTREE/HASHMYISAM/InnoDB 存储类型只支持BTREEMEMORY/HEAP支持两种一般情况下,有以下几种常用的索引:普通索引: INDEX--------- CREATE ...
  • 1.保持一致性,当数据库表进行DML操作时,同一行记录的页地址会发生改变,因非主键索引保存的是主键的值,无需进行更改; 2.节省存储空间,后续补充,不太清楚原因。 参考链接:...
  • 索引_存储结构

    千次阅读 2020-07-07 23:45:23
    ​​​​不同数据库使用的索引存储结构 聚簇索引 和 非聚簇索引 MongoDB 和Mysql 使用的索引 的 存储结构 B-Tree 和 B+Tree相关介绍 MySql 采用的是 B+Tree(真正的data都存放在最底层的叶子节点上)的存储...
  • Mysql 索引存放位置

    千次阅读 2021-08-07 14:52:35
    可以通过SHOW VARIABLES LIKE '%datadir%'查询mysql索引存放位置: 根据存储引擎不同,索引的文件类型也不同:
  • 索引中相同的值,存储的id是什么结构?在本篇文章中就跟你一一说明 一、组合索引的图示 话不多说,直接上图 上面是根据身高年龄建立的组合索引(height,age) 二、组合索引在B+树中的排序 以上图索引为例,组合索引...
  • elasticsearch 索引存储深入详解

    万次阅读 2016-08-09 20:57:57
    (1)早期ES1.X版本对ES索引存储介绍:原文地址: https://www.elastic.co/guide/en/elasticsearch/reference/1.4/index-modules-store.html ES1.X存储模块可以控制索引数据的存储方式,索引可以存储在内存和磁盘上...
  • 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存结构中。 索引结构和散列结构适用在外存与内存交互结构。 顺序存储:在计算机中用一组地址连续的存储单元依次...
  • mysql索引索引存储结构

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

    千次阅读 多人点赞 2020-08-14 09:49:45
    最困难的事情就是认识自己! 个人网站,欢迎访问! 前言: 本篇文章主要是阐述下 联合索引 在 B+Tree 上的实际存储...很多博客中都是说:联合索引在B+树上的 非叶子节点 中只会存储 联合索引 中的第一个索引字段 的.
  • mysql存储索引技术

    2011-12-23 08:38:25
    介绍mysql不同的存储引擎 以及 索引技术在mysql中的应用
  • MySQL数据库的存储引擎及索引

    千次阅读 2022-03-27 20:58:06
    MySQL存储引擎 MySQL的存储引擎有很多种,使用show engines命令查看MySQL支持的存储引擎 我们这里主要介绍一下InnoDB和MyISAM存储引擎 MyISAM存储引擎(mysql-5.1版本之前默认引擎) InnoDB存储引擎(mysql-...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,174,561
精华内容 469,824
关键字:

索引存储