精华内容
下载资源
问答
  • 数据库索引结构---T树的原理

    千次阅读 2011-06-09 21:08:00
    索引用于在查询时提高效率之用。可以为每张表的某个字段定义索引来提高在该字段上的查询效率。由于数据库要处理的数据量非常大,而...B-tree结构的主要目的是减少完成数据文件的索引查找所需要的磁盘I/O的数量。B-tre

    索引用于在查询时提高效率之用。可以为每张表的某个字段定义索引来提高在该字段上的查询效率。由于数据库要处理的数据量非常大,而内存因为价格昂贵,而容量有限,且必须满足一定的实时性,因而对其中的数据的存储及索引方式进行研究,找出有效的数据组织方式是非常有必要的。磁盘数据库系统的典型的索引技术是B-tree索引。B-tree结构的主要目的是减少完成数据文件的索引查找所需要的磁盘I/O的数量。B-tree通过控制节点内部的索引值达到这个目的,在节点中包含尽可能多的索引条目(增加一次磁盘I/O可以访问的索引条目)。
          另一方面,T-tree是针对主存访问优化的索引技术。T-tree是一种一个节点中包含多个索引条目的平衡二叉树,T-tree的索引项无论是从大小还是算法上都比B-tree精简得多。T-tree的搜索算法不分搜索的值在当前的节点还是在内存中的其他地方,每访问到一个新的索引节点,索引的范围减少一半。
          T树索引用来实现关键字的范围查询。T树是一棵特殊平衡的二叉树(AVL),它的每个节点存储了按键值排序的一组关键字。T树除了较高的节点空间占有率,遍历一棵树的查找算法在复杂程度和执行时间上也占有优势。现在T树己经成为内存数据库中最主要的一种索引方式。

    1.T树相关概念
         T树具有以下特点:①左子树与右子树之差不超过1,②在一个存储节点可以保存多个键值,它的最左与最右键值分别为这个节点的最小与最大键值,它的左子树仅仅包含那些键值小于或等于最小键值的一记录,同理右子树只包括那些键值大于或等于最大键值的记录,③同时拥有左右子树的节点被称为内部节点,只拥有一个子树的节点被称为半叶一,没有子树的节点被称为叶子,④为了保持空间的利用率,每一个内部节点都需要包含一个最小数目的键值。由此可知T树是一个每个结点含有多个关键字的平衡二叉树,每个节点内的关键字有序排列,左子树都要比根节点关键字小,右子树都要比根节点关键字大。
    在上述T树结点结构中,包含如下信息:
    (1) balance(平衡因子),其绝对值不大于1,balance =右子树高度-左子树高度;
    (2) Left_child_ptr和Right_child_ptr分别表示当前结点的左子树和右子树指针;
    (3) Max_Item表示结点中所能容纳的键值的最大数;
    (4)Key[0]至K[Max_Item-1]为结点内存放的关键字;
    (5)nItem是当前节点实际存储的关键字个数。
    对于T树有如下特征:
    (1)与AVL树相似,T树中任何结点的左右子树的高度之差最大为1;
    (2)与AVL树不同,T树的结点中可存储多个键值,并且这些键值排列有序;
    (3)T树结点的左子树中容纳的键值不大于该结点中的最左键值;右子树中容纳的键值不小于该结点中的最右键值;
    (4)为了保证每个结点具有较高的空间占用率,每个内部结点所包含的键值数目必须不小于某个指定的值,通常为(Max_Item-2)(Max_Item为结点中最大键值目)。

    2.T树索引的操作
          用T树作为索引方式主要完成三个工作:查找,插入,删除。其中插入和删除都是以查找为基础。下面分别介绍三种操作的流程。
    (1)T树的查找类似于二叉树,不同之处主要在于每一结点上的比较不是针对结点中的各个元素值,而是首先检查所要查找的目标键值是否包含在当前结点的最左键值和最右键值所确定的范围内,如果是的话,则在当前结点的键值列表中使用二分法进行查找;如果目标键值小于当前结点的最左键值,则类似地搜索当前结点的左孩子结点;如果目标键值大于当前结点的最右键值,则类似地搜索当前结点的右孩子结点。 
    (2)T树的插入是以查找为基础,应用查找操作定位目标键值插入位置,并记下查找过程所遇到的最后结点。如果查找成功,判断此结点中是否有足够的存储空间。如果有,则将目标键值插入结点中;否则将目标键值插入此结点,然后将结点中的最左键值插入到它的左子树中(此时是递归插入操作),之后结束;否则分配新结点,并插入目标键值;然后根据目标键值与结点的最大最小键值之间的关系,将新分配的结点链接为结点的左孩子或右孩子;对树进行检查,判断T树的平衡因子是否满足条件,如果平衡因子不满足则执行旋转操作。

    (3)T树的删除操作也是以查找为基础,应用查找操作定位目标键值。如果查找失败,则结束;否则令N为目标键值所在的结点,并从结点N中删除目标键值;删除节点后,如果结点N为空,则删除结点N,并对树的平衡因子进行检查,判断是否需要执行旋转操作;如果结点N中的键值数量少于最小值,则根据N的平衡因子决定从结点N的左子树中移出最大的键值或者右子树中移出最小值来填充。 

    3.T树索引实现关键技术
         实现T树索引即要实现T树的查找,插入和删除。其中又以查找为基础,对T树的维护也就是T树的旋转为关键。当由于插入或删除键值导致树的失衡,则要进行T树的旋转。使之重新达到平衡。
         在插入情况下,需要依次对所有沿着从新创建结点到根结点路径中的结点进行检查,直到出现如下两种情况之一时中止:某个被检查结点的两个子树高度相等,此时不需要执行旋转操作;某个被检查结点的两个子树的高度之差大于1,此时对该结点仅需执行一次旋转操作即可。
         在删除情况下,类似地需要依次对所有沿着从待删除结点的父结点到根结点路径中的结点进行检查,在检查过程中当发现某个结点的左右子树高度之差越界时,需要执行一次旋转操作。与插入操作不同的是,执行完旋转操作之后,检查过程不能中止,而是必须一直执行到检查完根结点。
         由此可以看出,对于插入操作,最多只需要一次旋转操作即可使T树恢复到平衡状态;而对于删除操作则可能会引起向上的连锁反应,使高层结点发生旋转,因而可能需要进行多次旋转操作。
         为了对T树进行平衡,需要进行旋转操作,旋转是T树中最关键也是最难的的操作,下面介绍T树旋转的技术。旋转可分为四种情况:由左孩子的左子树的插入(或者删除)引起的旋转记为LL旋转,类似有LR,RR及RL旋转。插入时的情况与删除类似。

    展开全文
  • 数据库索引的数据结构
  • 数据库索引存储结构

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

    主键索引(PRIMAY KEY):

           一个表中只能有一个主键,创建主键自动创建主键索引,该索引是唯一索引,其主键列的数据值不重复。建议使用INT型的自动增长主键,这样索引效率最高。

    唯一索引(UNIQUE):

           不允许索引列的值相同。系统在创建该索引时检查是否有重复的键值,并在每次使用INSERT或UPDATE语句添加数据时进行检查。索引结果再根据主键索引查询数据。

    复合索引(INDEX):

           多个列建立索引,复合索引在数据库操作期间所需的开销更小,可以代替多个单一索引;第一个字段作为条件时才能保证系统使用该索引。建议不超过2个字段的复合索引。

     

    B-Tree的存储结构(例如100条数据):

           在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。每个域的大小都相同。

     

     

    B+Tree的存储结构(例如100条数据):

           

           在B+Tree中key检索数据算法如同目录:首先从根节点进行二分查找,从左(小)边到右(大)匹配,找到key匹配成功的索引值,根据索引值对应的节点地址,进入节点地址key继续进行匹配,直到进入叶节点,再根据key获取数据。

           在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能。

           注意:每个索引的最小值,也就是子索引的最小值,依次类推,最后的子索引的最小值,也就是该数据页的key索引的最小值。最小值都是靠最左边排列。都是节点开始的第一个值。

           注意:叶节点的数据页存有邻近的数据页节点地址,可以通过数据页的节点直接进入邻近数据页,查询需要的主键索引值。 

    索引性能影响:

    • 插入:按顺序插入在尾部,对索引影响微乎其微,索引不用重新排列顺序,只需要添加顺序的记录即可。如果是中间插入,则影响索引顺序,索引需要重写排列顺序,导致性能下降。
    • 删除:尾部删除,对索引影响甚微,索引不用重新排列顺序,只要去除顺序尾部的记录即可。如果中间删除,则影响索引顺序,索引需要重写排列顺序。导致性能下降。
    • 更新:更新字段不包含索引列,性能不会降低。如果更新索引列,索引目录表将重写排列索引顺序,导致性能下降。

     

    索引规则:

    建立索引规则:

    • 数据量超过300的,经常与其他表进行连接的表,在连接字段上应该建立索引;表的主键、外键必须有索引;经常出现在Where子句中的字段,特别是大表的字段,应该建立索引;
    • 索引应该建在选择性高的字段类型的小字段上,比如INT类型字段;
    • 尽量不要对数据库中某个含有大量重复的值的字段建立索引。

    复合索引规则:

    • 复合索引的建立需要进行仔细分析,尽量考虑用单字段索引代替;如果需要复合索引,正确选择复合索引中的主列字段,一般是选择性高的字段类型的小字段上;
    • 复合索引的几个字段是否经常同时以AND方式出现在Where子句中?单字段查询是否极少甚至没有?如果是,则可以建立复合索引;否则考虑单字段索引;
    • 如果复合索引中包含的字段经常单独出现在Where子句中,则分解为多个单字段索引;
    • 如果复合索引所包含的字段超过3个,那么仔细考虑其必要性,考虑减少复合的字段;复合索引最好只使用2个字段,索引本身也有I/O、内存、存储开销。复合索引字段越少越好。
    • 如果既有单字段索引,又有这几个字段上的复合索引,一般可以删除复合索引;

    索引操作影响:

    • 频繁进行数据操作的表,不要建立太多的索引;删除无用的索引,避免对执行计划造成负面影响;
    • 表上建立的每个索引都会增加存储开销,索引对于插入、删除、更新操作也会增加处理上的开销。另外,过多的复合索引,在有单字段索引的情况下,一般都是没有存在价值的;相反,还会降低数据增加删除时的性能,特别是对频繁更新的表来说,负面影响更大。
    展开全文
  • 数据库 索引

    2020-12-14 18:21:27
    文章目录数据库 索引1、概述2、索引的种类3、索引的底层实现原理3.1 索引的基础知识3.1 索引提高检索速度3.3 哈希索引4、聚集索引与非聚集索引4.1 聚集索引4.2 非聚集索引4.3 覆盖索引5、索引的最左分配原则6、总结 ...
  • 数据库索引

    千次阅读 多人点赞 2019-08-20 22:49:54
    数据库索引 文章目录数据库索引定义优缺点索引类型建立普通索引或组合索引适合建立索引的情况索引失效的sql 定义 索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息...

    数据库索引

    定义

    索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。数据库索引好比是一本书前面的目录,能加快数据库的查询速度。索引分为聚簇索引和非聚簇索引两种,聚簇索引是按照数据存放的物理位置为顺序的,而非聚簇索引就不一样了;聚簇索引能提高多行检索的速度,而非聚簇索引对于单行的检索很快。

    本人对于索引理解较浅,如有错误或不足的地方,欢迎指正,共同学习。

    优缺点

    优点

    • 在设计数据库时,通过创建一个惟一的索引,能够在索引和信息之间形成一对一的映射式的对应关系,增加数据的惟一性特点。

    • 能提高数据的搜索及检索速度,符合数据库建立的初衷。

    • 能够加快表与表之间的连接速度,这对于提高数据的参考完整性方面具有重要作用。

    • 在信息检索过程中,若使用分组及排序子句进行时,通过建立索引能有效的减少检索过程中所需的分组及排序时间,提高检索效率。

    • 建立索引之后,在信息查询过程中可以使用优化隐藏器,这对于提高整个信息检索系统的性能具有重要意义。

      缺点

    • 在数据库建立过程中,需花费较多的时间去建立并维护索引,特别是随着数据总量的增加,所花费的时间将不断递增。

    • 在数据库中创建的索引需要占用一定的物理存储空间,这其中就包括数据表所占的数据空间以及所创建的每一个索引所占用的物理空间,如果有必要建立起聚簇索引,所占用的空间还将进一步的增加

    • 在对表中的数据进行修改时,例如对其进行增加、删除或者是修改操作时,索引还需要进行动态的维护,这给数据库的维护速度带来了一定的麻烦。

    索引类型

    根据数据库的功能,可以在数据库设计器中创建三种索引唯一索引、主键索引和聚集索引。有关数据库所支持的索引功能的详细信息,请参见数据库文档。

    提示:尽管唯一索引有助于定位信息,但为获得最佳性能结果,建议改用主键唯一约束

    唯一索引

    UNIQUE
    create unique index 索引名 on 表名(表中的列[(length)])
    alter table 表名 add UNIQUE 索引名 (表中的列[(length)])
    

    唯一索引是不允许其中任何两行具有相同索引值的索引。当现有数据中存在重复的键值时,大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如,如果在employee表中职员的姓(lname)上创建了唯一索引,则任何两个员工都不能同姓。

    主键索引

    PRIMARY KEY  -- 建表时自接指定
    alert table 表名 add primary key (表中的列[(length)])
    

    数据库表经常有一列或多列组合,其值唯一标识表中的每一行。该列称为表的主键。在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。

    聚集索引

    在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。如果某索引不是聚集索引,则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比,聚集索引通常提供更快的数据访问速度。聚集索引和非聚集索引的区别,如字典默认按字母顺序排序(物理顺序),读者如知道某个字的读音可根据字母顺序快速定位(索引顺序与物理顺序相同)。因此聚集索引和表的内容是在一起的。如读者需查询某个生僻字,则需按字典前面的索引,举例按偏旁进行定位,找到该字对应的页数,再打开对应页数找到该字。这种通过两个地方而查询到某个字的方式就如非聚集索引。

    建立普通索引或组合索引

    create index 索引名 on 表名(列名);
    create index 索引名 on 表名(列名1,列名2,..); -- 组合索引
    

    组合索引 最左前缀 原则

    个人理解 例如 : create index index_abc on TEST_TAB(a,b,c); 相当于建立了 a, ab, abc 三组索引。

    只要某查询条件中包含复合索引中的第一个列,该查询就会走索引,如果不包含,就不会走索引

    有博主的实验 https://blog.csdn.net/tw7752/article/details/44595281

    适合建立索引的情况

    • 经常作为查询条件的列 (where)
    • 经常用于表连接的列,如外键 (join)
    • 经常用于排序的列 (order)

    索引失效的sql

    • 组合索引使用 or 索引失效 如 a=1 or b=2 or c=3

    • 索引条件为 is null / is not null 索引失效(看清况,测试过 null 比较多时, not null 会走索引)

    • 索引条件 like ‘%xxx’, 索引失效; like ‘xxxx%’ 索引生效

    • 索引列参加计算 如 t.score/10 > 10 失效, 应改成 t.score > 10*10

    • 索引列不要使用NOT ( != 、 <> )如 t.score! = 10 失效,改成:t.score > 10 or t.score < 10

    • 索引列上发生类型转换, 例如 VARCHAR2 类型的索引列 ,写成 where id = 1 ,应该 改成 where id = ‘1’ ( oracle实验)

    最好是 看一下sql的执行计划,看看是否走了索引。

    Oracle查看sql执行计划

    explain plan for  
    select xxx from tablename where xxx ;
    
    select * from table(dbms_xplan.display); 
    

    索引的原理 请看大神博客 https://blog.csdn.net/sinat_30186009/article/details/52169057

    组合索引设计 https://blog.csdn.net/bless2015/article/details/84035845

    展开全文
  • 数据库索引及其数据结构

    千次阅读 2018-04-08 20:26:04
    数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种...

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

    在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

    为表设置索引要付出代价的:一是增加了数据库的存储空间,二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。

     

    上图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

     

    创建索引可以大大提高系统的性能。

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

    第二,可以大大加快数据的检索速度,这也是创建索引的最主要的原因。

    第三,可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。

    第四,在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。

    第五,通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。 

     

    也许会有人要问:增加索引有如此多的优点,为什么不对表中的每一个列创建一个索引呢?因为,增加索引也有许多不利的方面。

    第一,创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。

    第二,索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要的空间就会更大。

    第三,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

     

    索引是建立在数据库表中的某些列的上面。在创建索引的时候,应该考虑在哪些列上可以创建索引,在哪些列上不能创建索引。一般来说,应该在这些列上创建索引:在经常需要搜索的列上,可以加快搜索的速度;在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构;在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度;在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的;在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间;在经常使用在WHERE子句中的列上面创建索引,加快条件的判断速度。

     

    同样,对于有些列不应该创建索引。一般来说,不应该创建索引的的这些列具有下列特点:

    第一,对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为,既然这些列很少使用到,因此有索引或者无索引,并不能提高查询速度。相反,由于增加了索引,反而降低了系统的维护速度和增大了空间需求。

    第二,对于那些只有很少数据值的列也不应该增加索引。这是因为,由于这些列的取值很少,例如人事表的性别列,在查询的结果中,结果集的数据行占了表中数据行的很大比例,即需要在表中搜索的数据行的比例很大。增加索引,并不能明显加快检索速度。

    第三,对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。

    第四,当修改性能远远大于检索性能时,不应该创建索引。这是因为,修改性能和检索性能是互相矛盾的。当增加索引时,会提高检索性能,但是会降低修改性能。当减少索引时,会提高修改性能,降低检索性能。因此,当修改性能远远大于检索性能时,不应该创建索引。

     

    根据数据库的功能,可以在数据库设计器中创建三种索引:唯一索引、主键索引和聚集索引

     

    唯一索引 

     

    唯一索引是不允许其中任何两行具有相同索引值的索引。

     

    当现有数据中存在重复的键值时,大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如,如果在employee表中职员的姓(lname)上创建了唯一索引,则任何两个员工都不能同姓。

     

    主键索引

     

    数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。

     

    在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。

     

    聚集索引

     

    在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。

     

    如果某索引不是聚集索引,则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比,聚集索引通常提供更快的数据访问速度。

     

     

     

    局部性原理与磁盘预读

     

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理当一个数据被用到时,其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

    B-/+Tree索引的性能分析

    到这里终于可以分析B-/+Tree索引的性能了。

    上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

    每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

    B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

    而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

     

    综上所述,用B-Tree作为索引结构效率是非常高的。

     

     

    应该花时间学习B-树和B+树数据结构

    =============================================================================================================

     

    1)B树

    B树中每个节点包含了键值和键值对于的数据对象存放地址指针,所以成功搜索一个对象可以不用到达树的叶节点。

    成功搜索包括节点内搜索和沿某一路径的搜索,成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。

     

    在B树中查找给定关键字的方法是:首先把根结点取来,在根结点所包含的关键字K1,…,kj查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查的关键字在某个Ki或Ki+1之间,于是取Pi所指的下一层索引节点块继续查找,直到找到,或指针Pi为空时查找失败。

     

     

    2)B+树

     

    B+树非叶节点中存放的关键码并不指示数据对象的地址指针,非也节点只是索引部分。所有的叶节点在同一层上,包含了全部关键码和相应数据对象的存放地址指针,且叶节点按关键码从小到大顺序链接。如果实际数据对象按加入的顺序存储而不是按关键码次数存储的话,叶节点的索引必须是稠密索引,若实际数据存储按关键码次序存放的话,叶节点索引时稀疏索引。

     

    B+树有2个头指针,一个是树的根节点,一个是最小关键码的叶节点。

    所以 B+树有两种搜索方法:

    一种是按叶节点自己拉起的链表顺序搜索。

    一种是从根节点开始搜索,和B树类似,不过如果非叶节点的关键码等于给定值,搜索并不停止,而是继续沿右指针,一直查到叶节点上的关键码。所以无论搜索是否成功,都将走完树的所有层。

    B+ 树中,数据对象的插入和删除仅在叶节点上进行。

     

     

    这两种处理索引的数据结构的不同之处:
    a,B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。
    b,因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
    c,B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。

    展开全文
  • 前面两篇文章 《解析B+树比B树更加适合做数据库索引的原因 》 和《从底层解析B+索引提高查询速度的原因》是从数据结构的角度分析了B+索引,并分别介绍了B+索引在两个主流存储引擎InnoDB和MyISAM中的实现。...
  • 数据库常见索引结构

    千次阅读 2019-07-12 15:18:42
    同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;   实际使用的B树都是在原B树的基础上加上平衡算法,即“平衡...
  •   说到数据库优化脱口而出就是添加索引,如果不会用请移步《解锁数据库系列》数据库索引已为你备好!掌握数据结构,就可以掌握索引的底层原理,我们应当有**路漫漫其修远兮,吾将上下而求索**的态度,本文将探究...
  • 索引的数据结构分析,数据库面试到索引最常见的问题分析,我总结了一下。
  • 1.什么是索引?为什么要用索引? 1.1索引的含义 1.2为什么用? 2.索引的作用与缺点 2.1作用 2.2缺点 3.索引的使用场景 3.1应创建索引的场景 3.2不应创建索引的场景 4.索引的分类与说明 4.1主键索引 ...
  • 数据库索引使用的数据结构

    千次阅读 2017-09-01 00:07:45
    数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种...
  • 数据库索引与数据库作业

    千次阅读 2018-05-08 10:21:52
    数据库索引是对数据库表中一列或多列进行排序的一种结构,使用索引可以快速访问数据库表中的特定信息。数据库索引就像书的目录,能加快数据库的查询速度。索引分为聚簇索引(聚集索引)和非聚簇索引(非聚集索引)。...
  • 深入理解数据库索引

    千次阅读 2019-02-14 07:19:17
    前言:数据库和数据库索引这两个东西是在服务器端开发领域应用最为广泛的两个概念,熟练使用数据库和数据库索引是后端开发人员在行业内生存的必备技能。数据库索引是用来提高数据库表的数据查询速度的。 一、索引...
  • 数据库索引设计与优化》提供了一种简单、高效、通用的关系型数据库索引设计方法。作者通过系统的讲解及大量的案例清晰地阐释了关系型数据库的访问路径选择原理,以及表和索引的扫描方式,详尽地讲解了如何快速地...
  • mysql进阶(二十七)数据库索引原理

    万次阅读 2016-10-13 20:20:38
      第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。   第二部分结合MySQL数据库中InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。   第三部分讨论...
  • 数据库索引总结.xmind

    2019-10-23 22:23:50
    数据库索引总结,索引的作用?索引的注意事项?数据库索引结构
  • 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文...
  • sql 数据库慢 重新构建索引结构
  • 这个问题其实还是很有趣的,我在上一篇...1、为什么数据库索引不能用二叉排序树; 2、为什么数据库索引不能用红黑树; 本篇文章增加了: 1、为什么不能使用哈希表; 2、为什么不能使用B-树; 3、为什么能使用B+树。
  • MySQL数据库索引

    万次阅读 多人点赞 2018-09-23 09:31:41
    索引有哪些结构 数据库有哪些索引 唯一索引 聚簇索引与非聚簇索引 全文索引 使用索引一定能提高查询性能吗? 哪些情况下设置了索引但是无法使用 哪些情况下需要设置索引、哪些情况下不需要 什么情况下应该...
  • 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 425,575
精华内容 170,230
关键字:

数据库索引结构