精华内容
下载资源
问答
  • 数据结构 Hash表(哈希表)

    万次阅读 多人点赞 2018-05-20 01:23:34
    参考链接:数据结构(严蔚敏) 什么是Hash表 要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都先从根节点进行查找,从节点取出...

    参考链接:数据结构(严蔚敏)

    一、什么是Hash表

    要想知道什么是哈希表,那得先了解哈希函数
    哈希函数

    对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种函数H,根据这个函数和查找关键字key,可以直接确定查找值所在位置,而不需要一个个比较。这样就**“预先知道”**key所在的位置,直接找到数据,提升效率。

    地址index=H(key)
    说白了,hash函数就是根据key计算出应该存储地址的位置,而哈希表是基于哈希函数建立的一种查找表

    二、哈希函数的构造方法

    根据前人经验,统计出如下几种常用hash函数的构造方法:
    直接定制法
    哈希函数为关键字的线性函数如 H(key)=a*key+b
    这种构造方法比较简便,均匀,但是有很大限制,仅限于地址大小=关键字集合的情况
    使用举例:
    假设需要统计中国人口的年龄分布,以10为最小单元。今年是2018年,那么10岁以内的分布在2008-2018,20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据,那么关键字应该是2018,2008,1998……
    那么可以构造哈希函数H(key)=(2018-key)/10=201-key/10
    那么hash表建立如下

    index key 年龄 人数(假设数据)
    0 2018 0-10 200W
    1 2008 10-20 250W
    2 1998 20-30 253W
    3 1988 30-40 300W
    ……

    数字分析法
    假设关键字集合中的每个关键字key都是由s位数字组成(k1,k2,,knk_1,k_2,……,k_n),分析key中的全体数据,并从中提取分布均匀的若干位或他们的组合构成全体

    使用举例
    我们知道身份证号是有规律的,现在我们要存储一个班级学生的身份证号码,假设这个班级的学生都出生在同一个地区,同一年,那么他们的身份证的前面数位都是相同的,那么我们可以截取后面不同的几位存储,假设有5位不同,那么就用这五位代表地址。
    H(key)=key%100000
    此种方法通常用于数字位数较长的情况,必须数字存在一定规律,其必须知道数字的分布情况,比如上面的例子,我们事先知道这个班级的学生出生在同一年,同一个地区。
    平方取中法
    如果关键字的每一位都有某些数字重复出现频率很高的现象,可以先求关键字的平方值,通过平方扩大差异,而后取中间数位作为最终存储地址。
    使用举例
    比如key=1234 1234^2=1522756 取227作hash地址
    比如key=4321 4321^2=18671041 取671作hash地址
    这种方法适合事先不知道数据并且数据长度较小的情况
    折叠法
    如果数字的位数很多,可以将数字分割为几个部分,取他们的叠加和作为hash地址
    使用举例
    比如key=123 456 789
    我们可以存储在61524,取末三位,存在524的位置
    该方法适用于数字位数较多且事先不知道数据分布的情况
    除留余数法用的较多
    H(key)=key MOD p (p<=m m为表长)
    很明显,如何选取p是个关键问题。

    使用举例
    比如我们存储3 6 9,那么p就不能取3
    因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
    p应为不大于m的质数或是不含20以下的质因子的合数,这样可以减少地址的重复(冲突)

    比如key = 7,39,18,24,33,21时取表长m为9 p为7 那么存储如下

    index 0 1 2 3 4 5 6 7 8
    key 7 21(冲突后移) 24 *39* 18(冲突后移) 33冲突后移)
    **随机数法** H(key) =Random(key) 取关键字的随机函数值为它的散列地址

    hash函数设计的考虑因素

    1.计算散列地址所需要的时间(即hash函数本身不要太复杂)
    2.关键字的长度
    3.表长
    4.关键字分布是否均匀,是否有规律可循
    5.设计的hash函数在满足以上条件的情况下尽量减少冲突

    三、哈希冲突

    即不同key值产生相同的地址,H(key1)=H(key2)
    比如我们上面说的存储3 6 9,p取3是
    3 MOD 3 == 6 MOD 3 == 9 MOD 3
    此时3 6 9都发生了hash冲突

    哈希冲突的解决方案

    不管hash函数设计的如何巧妙,总会有特殊的key导致hash冲突,特别是对动态查找表来说。
    hash函数解决冲突的方法有以下几个常用的方法
    1.开放定制法
    2.链地址法
    3.公共溢出区法
    建立一个特殊存储空间,专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
    4.再散列法
    准备若干个hash函数,如果使用第一个hash函数发生了冲突,就使用第二个hash函数,第二个也冲突,使用第三个……
    重点了解一下开放定制法和链地址法

    开放定制法

    首先有一个H(key)的哈希函数
    如果H(key1)=H(keyi)
    那么keyi存储位置Hi=(H(key)+di)MODmH_i=(H(key)+d_i)MOD mm为表长
    did_i有三种取法
    1)线性探测再散列
    di=cid_i=c*i
    2)平方探测再散列
    di=12,12,22,22d_i=1^2,-1^2,2^2,-2^2……
    3)随机探测在散列(双探测再散列)
    did_i是一组伪随机数列
    注意
    增量di应该具有以下特点(完备性):产生的Hi(地址)均不相同,且所产生的s(m-1)个Hi能覆盖hash表中的所有地址

    • 平方探测时表长m必须为4j+3的质数(平方探测表长有限制)
    • 随机探测时m和di没有公因子(随机探测di有限制)
      三种开放定址法解决冲突方案的例子

    废话不多说,上例子就明白了
    有一组数据
    19 01 23 14 55 68 11 86 37要存储在表长11的数组中,其中H(key)=key MOD 11
    那么按照上面三种解决冲突的方法,存储过程如下:
    (表格解释:从前向后插入数据,如果插入位置已经占用,发生冲突,冲突的另起一行,计算地址,直到地址可用,后面冲突的继续向下另起一行。最终结果取最上面的数据(因为是最“占座”的数据))
    线性探测再散列
    我们取di=1,即冲突后存储在冲突后一个位置,如果仍然冲突继续向后

    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 19 86
    23冲突 23
    68冲突 68冲突 68
    11冲突 11冲突 11冲突 11冲突 11冲突 11
    37冲突 37冲突 37
    最终存储结果 55 1 23 14 68 11 37 19 86
    **平方探测再散列**
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 37 19 86
    23冲突 H(23)+1
    H(68)-1冲突 68冲突 H(68)+1冲突 H(68)+4
    11冲突 H(11)+1冲突 H(11)-1
    最终存储结果 55 1 23 14 37 68 19 86 11
    **随机探测在散列(双探测再散列)** 发生冲突后 H(key)‘=(H(key)+di)MOD m 在该例子中 H(key)=key MOD 11 我们取di=key MOD 10 +1 则有如下结果:
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 68 14 19 86
    23冲突 H(23)+3+1
    11冲突 H(11)+1+1冲突 H(11)+1+1+1+1
    (H(37)+8)模11冲突 37冲突 (H(37)+8+8+8)模11 (H(37)+8+8)模11冲突
    最终存储结果 55 1 68 14 23 11 37 19 86

    链地址法

    产生hash冲突后在存储数据后面加一个指针,指向后面冲突的数据
    上面的例子,用链地址法则是下面这样:

    这里写图片描述
    四、hash表的查找

    查找过程和造表过程一致,假设采用开放定址法处理冲突,则查找过程为:
    对于给定的key,计算hash地址index = H(key)
    如果数组arr【index】的值为空 则查找不成功
    如果数组arr【index】== key 则查找成功
    否则 使用冲突解决方法求下一个地址,直到arr【index】== key或者 arr【index】==null

    hash表的查找效率

    决定hash表查找的ASL因素:
    1)选用的hash函数
    2)选用的处理冲突的方法
    3)hash表的饱和度,装载因子 α=n/m(n表示实际装载数据长度 m为表长)
    一般情况,假设hash函数是均匀的,则在讨论ASL时可以不考虑它的因素
    hash表的ASL是处理冲突方法和装载因子的函数
    前人已经证明,查找成功时如下结果:

    这里写图片描述
    可以看到无论哪个函数,装载因子越大,平均查找长度越大,那么装载因子α越小越好?也不是,就像100的表长只存一个数据,α是小了,但是空间利用率不高啊,这里就是时间空间的取舍问题了。通常情况下,认为α=0.75是时间空间综合利用效率最高的情况。

    上面的这个表可是特别有用的。假设我现在有10个数据,想使用链地址法解决冲突,并要求平均查找长度<2
    那么有1+α/2 <2
    α<2
    即 n/m<2 (n=10)
    m>10/2
    m>5 即采用链地址法,使得平均查找长度< 2 那么m>5

    之前我的博客讨论过各种树的平均查找长度,他们都是基于存储数据n的函数,而hash表不同,他是基于装载因子的函数,也就是说,当数据n增加时,我可以通过增加表长m,以维持装载因子不变,确保ASL不变。
    那么hash表的构造应该是这样的:

    这里写图片描述
    五、hash表的删除

    首先链地址法是可以直接删除元素的,但是开放定址法是不行的,拿前面的双探测再散列来说,假如我们删除了元素1,将其位置置空,那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据,比如-1

    展开全文
  • 索引数据结构是什么?2.1可以是二叉搜索树吗?2.2可以是哈希表吗?2.3可以是B-树吗?2.4可以是B+树吗?2.5explain查看SQL的执行3.什么是事务?3.1概念3.2如何使用3.2.1 commit全部成功3.2.2rollback全部失败3.3事务的...

    1.什么是数据库索引?

    1.1概念

    • 索引是一种特殊的文件,包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引,并指定索引的类型,各类索引有各自的数据结构实现。

    1.2作用

    1. 数据库中的表、数据、索引之间的关系,类似于书架上的图书、书籍内容和书籍目录的关系。
    2. 索引所起的作用类似书籍目录,可用于快速定位、检索数据。
    3. 如果没有索引,在数据库中进行查找就要把整个表遍历一遍,很耗时.
    4. 索引对于提高数据库的性能 (主要是提高查找效率,修改增加删除效率还会有所下降) 有很大的帮助。
    5. 本质上索引就是为了避免数据库进行顺序查找,提高查找效率.

    1.3使用场景

    • 要考虑对数据库表的某列或某几列创建索引,需要考虑以下几点:
    1. 数据量较大,且经常对这些列进行条件查询。
    2. 该数据库表的插入操作,及对这些列的修改操作频率较低。
    3. 索引会占用额外的磁盘空间。(用空间效率换取时间效率)
      满足以上条件时,考虑对表中的这些字段创建索引,以提高查询效率。
      反之,如果非条件查询列,或经常做插入、修改操作,或磁盘空间不足时,不考虑创建索引。

    1.4如何使用

    • 创建主键约束(PRIMARY KEY)、唯一约束(UNIQUE)、外键约束(FOREIGN KEY)时,会自动创建对应列的索引。
    • 查看索引
    mysql> show index from student;
    +---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    | Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
    +---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    | student |          0 | PRIMARY  |            1 | id          | A         |           1 |     NULL | NULL   |      | BTREE      |         |               |
    +---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    1 row in set (0.00 sec)
    
    • 创建索引
      对于非主键、非唯一约束、非外键的字段,可以创建普通索引
    mysql> show index from student;
    +---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    | Table   | Non_unique | Key_name         | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
    +---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    | student |          0 | PRIMARY          |            1 | id          | A         |           1 |     NULL | NULL   |      | BTREE      |         |               |
    | student |          1 | idx_student_name |            1 | name        | A         |           1 |     NULL | NULL   | YES  | BTREE      |         |               |
    +---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    2 rows in set (0.00 sec)
    
    • 删除索引
      如果是主键、唯一约束、外键索引不可删除
    mysql> drop index idx_student_name on student;
    Query OK, 0 rows affected (0.01 sec)
    Records: 0  Duplicates: 0  Warnings: 0
    
    mysql> show index from student;
    +---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    | Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
    +---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    | student |          0 | PRIMARY  |            1 | id          | A         |           1 |     NULL | NULL   |      | BTREE      |         |               |
    +---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    1 row in set (0.00 sec)
    

    2.索引的数据结构是什么?

    2.1可以是二叉搜索树或者红黑树吗?

    • 不可以
    1. 二叉搜索树的平均查找效率是O(logN)
    2. 如果数据很多的话,二叉搜索树最多俩个分支,所以树的深度会很大,查找效率其实不高
    3. 如果是查找范围的时候还需要对二叉搜索树进行中序遍历 (因为二叉搜索树中序遍历是有序序列) 又不是很高效O(N)
      在这里插入图片描述

    2.2可以是哈希表吗?

    • 不可以
    1. 如果是处理相等情况,哈希表很高效
    2. 但是哈希表不可以处理其他逻辑,比如范围查找 > >= < <= between and
    3. 因为哈希的查找是把key带入哈希函数得到下标,再根据下标取对应的链表,再去遍历链表比较key是否相等,无法进行范围查找

    2.3可以是B-树吗?

    • 本质可以,但为了更高的效率不选它
    • B-树与二叉树差异
    1. 为了结点不是2叉而是N叉
    2. 为了结点不是存储一个数据,而是可能存储多个数据
    3. 每个节点存储数据的个数和该节点的度是有关系的 度=存储数据的个数+1
    4. 此时在B-树上查找就是一个N分查找,效率比二叉树还高
    5. 由于每个及节点存储了多个数据,每个节点又有多个度,所以和二叉树相比,B-树的高度会低很多,查找起来效率一会高一下.而且简单的范围查找会容易一些.
      在这里插入图片描述
    6. 因为其叶子 非叶子 都是存储数据都要放在磁盘上,所以遇到较复杂的范围查找,需要读取磁盘的次数还是较高,所以效率还不是很好
      在这里插入图片描述

    2.4可以是B+树吗?

    • 真实的索引结构
    • 与B-树相比的差异
    1. 每一层的元素之间都链接在一起
    2. 数据(表的一行记录)只存在叶子节点上,非叶子节点只保存一些辅助查找的边界信息
    3. 查询任一条记录都比较平均,不会出现效率差异很大的情况
    4. 不需要额外进行中序遍历,遍历叶子节点就是中序结果,所以处理范围查找很高效
    5. 叶子放在磁盘上,非叶子放在内存中,减少了访问磁盘的次数,查找也就更高效了,而且索引在内存中实际开销有不高
    6. 索引引起的效果就是加快查找效率, 减慢插入删除修改的效率 (因为需要同步调整索引结果)
    7. 索引也会占用额外空间(本质上使用空间换取时间)
    8. 给具体表中某列加索引的时候,加在主键的索引和加在其他列的索引是截然不同的.
    9. 主键索引的叶子结点value存的是表的一行完整数据, 其他索引的叶子节点value只存的是主键的信息(如id)
      在这里插入图片描述

    2.5explain查看SQL的执行

    • 帮助我们分析SQL的执行过程,能够看到是否使用索引,以及使用了哪个索引
    • key等于null表示没用到索引,否则会显示用到哪个索引
    mysql> explain select * from student where id = 1;
    +----+-------------+---------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
    | id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref   | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
    |  1 | SIMPLE      | student | NULL       | const | PRIMARY       | PRIMARY | 4       | const |    1 |   100.00 | NULL  |
    +----+-------------+---------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
    1 row in set, 1 warning (0.00 sec)
    

    3.什么是事务?

    3.1概念

    • 事务指逻辑上的一组操作,组成这组操作的各个单元,要么全部成功,要么全部失败。
    • 在不同的环境中,都可以有事务。对应在数据库中,就是数据库事务。

    3.2如何使用

    (1)开启事务:start transaction;
    (2)执行多条SQL语句
    (3)回滚或提交:rollback/commit;
    说明:rollback即是全部失败,commit即是全部成功

    3.2.1 commit全部成功

    在这里插入图片描述

    mysql> select * from student;
    +----+-----------+---------+
    | id | name      | classId |
    +----+-----------+---------+
    |  1 | 张翼德    |      10 |
    |  2 | 刘备      |      10 |
    +----+-----------+---------+
    2 rows in set (0.00 sec)
    
    mysql> start transaction;
    Query OK, 0 rows affected (0.00 sec)
    
    mysql> update student set classId = classId + 1 where id = 1;
    Query OK, 1 row affected (0.00 sec)
    Rows matched: 1  Changed: 1  Warnings: 0
    
    mysql> update student set classId = classId - 1 where id = 2;
    Query OK, 1 row affected (0.00 sec)
    Rows matched: 1  Changed: 1  Warnings: 0
    
    mysql> commit;
    Query OK, 0 rows affected (0.00 sec)
    
    mysql> select * from student;
    +----+-----------+---------+
    | id | name      | classId |
    +----+-----------+---------+
    |  1 | 张翼德    |      11 |
    |  2 | 刘备      |       9 |
    +----+-----------+---------+
    2 rows in set (0.00 sec)
    

    3.2.2rollback全部失败

    在这里插入图片描述

    mysql> select * from student;
    +----+-----------+---------+
    | id | name      | classId |
    +----+-----------+---------+
    |  1 | 张翼德    |      12 |
    |  2 | 刘备      |       8 |
    +----+-----------+---------+
    2 rows in set (0.00 sec)
    
    mysql> start transaction;
    Query OK, 0 rows affected (0.00 sec)
    
    mysql> update student set classId = classId + 1 where id = 1;
    Query OK, 1 row affected (0.00 sec)
    Rows matched: 1  Changed: 1  Warnings: 0
    
    mysql> update student set classId = classId - 1 where id = 2;
    Query OK, 1 row affected (0.00 sec)
    Rows matched: 1  Changed: 1  Warnings: 0
    
    mysql> rollback;
    Query OK, 0 rows affected (0.01 sec)
    
    mysql> select * from student;
    +----+-----------+---------+
    | id | name      | classId |
    +----+-----------+---------+
    |  1 | 张翼德    |      12 |
    |  2 | 刘备      |       8 |
    +----+-----------+---------+
    2 rows in set (0.00 sec)
    

    3.3事务的特点

    1. 原子性(最重要): 事务中的若干个操作,要么全部执行成功,要么全部不执行(本质上不是全部不执行,那是把已执行的步骤回滚(rollback)回去,借助逆向操作,把原来操作造成的影响进行还原)
    2. 一致性: 执行事务前后,数据库始终处于一种合法的状态
    3. 持久性: 事务一旦执行完毕, 此时对于数据库的修改是持久生效的
    4. 隔离性:较复杂难点,后面解释.
      MySQL~详细介绍事务的一个重要特性–隔离性 (解决脏读、不可重复读、幻读)
    展开全文
  • 哈希表、哈希索引详解

    千次阅读 2019-09-29 09:43:24
    哈希表(也叫散列表),根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 ...

    1、什么是哈希表?

       哈希表(也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    简单地说,哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。

    addr=f(key)

    这里的对应关系f称为散列函数,又称为哈希(Hash函数),采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。

     

    2、使用哈希查找的两个步骤

    使用哈希函数将被查找的转换为数组索引。根据数组索引直接取到数据的内存地址。在理想的情况下,不同的键会被转换为不同的索引值,但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突。

     

    3、处理冲突的方法

    • 链地址法(拉链法)常用
    • 开放定址法
    • 再散列法
    • 建立一个公共溢出区

     

    4、哈希函数的构造方法

    构造哈希函数的原则是:①函数本身便于计算;②计算出来的地址分布均匀,即对任一关键字k,f(k) 对应不同地址的概率相等,目的是尽可能减少冲突。

    • 直接定址法
    • 除留余数法
    • 乘余取整法
    • 数字分析法
    • 平方取中法
    • 折叠法
    • 随机数法

     

    5、B+树索引和哈希索引的明显区别是:

    • 如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据;

    • 从示意图中也能看到,如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;

    • 同理,哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询);

    • 哈希索引也不支持多列联合索引的最左匹配规则

    • B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题

    在MySQL中,只有Memory引擎显式支持哈希索引。这也是Memory引擎表的默认索引类型,Memory引擎同时也支持B-Tree索引。
     

    展开全文
  • 面试官:MySQL索引的存储结构是什么? 面试者:是B+树。 面试官:为什么不是B树、二叉树、哈希表? 面试者:%……&(&……(懵逼中) 面试官:MySQL有哪几种索引? 面试者:主键索引、唯一索引、联合索引、...

    前言

    面试官:MySQL索引的存储结构是什么?
    面试者:是B+树。
    面试官:为什么不是B树、二叉树、哈希表?
    面试者:%……&&……(懵逼中)

    面试官:MySQL有哪几种索引?
    面试者:主键索引、唯一索引、联合索引、普通索引。
    面试官:什么是聚簇索引、非聚簇索引、覆盖索引、索引下推、最左原则?
    面试者:%……&&……(懵逼中)

    接下来我们就通过了解B+树去全面解决这几个问题。

    一、B+树的数据结构

    树的概念我的就赘述了,其他文章都写的非常清楚了。
    我们要注意的一个点:InnoDB和MyIsam在存储的区别。

    InnoDB
    主键索引的存储结构是:叶子节点存储了主键值和其他字段数据值
    其他索引的存储结构是:叶子节点存储了索引值和主键索引值

    区别是其他索引存的是主键索引值

    MyIsam
    索引的存储结构是:叶子节点存储了主键值和数据记录的地址

    主键索引和其他索引存储结构是一样的

    说B+树之前先说说B树,B+树是在B树基础上优化来的。

    B树索引格式

    在这里插入图片描述
    B树的缺点:会因为树的深度过深而造成IO次数变多,从而影响查询效率。

    再来看看B+树索引格式
    在这里插入图片描述
    B+树跟B树区别:B+树数据只存在叶子节点,这样每个节点存储的数据会变多,从而存储大量数据时树的深度会比B树少很多很多,基本三层B+树就能存储千万级别的数据。所以MySQL才会选择B+树,减少磁盘IO,提高读取效率。不选二叉树或红黑树都是同样的道理。

    那为什么不选哈希表呢?

    • 哈希索引没办法利用索引完成排序。
    • 不能进行多字段查询。
    • 在有大量重复键值的情况下,哈希索引的效率也是极低的(出现哈希碰撞问题)。
    • 不支持范围查询。

    回表是什么
    二级索引存储的是主键ID,所以通过二级所以查询的过程是:先去查主键ID,再通过主键ID去查询数据,这个过程称为回表。

    二、索引相关

    在这里插入图片描述

    聚簇索引InnoDB的主键索引是聚簇索引。一个表中只能拥有一个聚集索引。

    非聚簇索引InnoDB的普通索引是非聚簇索引MyIsam的索引就是非聚簇索引。

    覆盖索引:select的数据列只用从索引中就能够取得,不必从数据表中读取,即查询列要被所使用的索引覆盖。

    不建议使用select * 查询也是有这个部分这个原因。
    还有优化 limit 90000,10这种SQL语句核心也是使用覆盖索引提高效率。

    索引下推:只能用于二级索引。

    mysql>select * from user where name like '张%' and age > 10
    假设创建了联合索引(name,age)
    

    这条SQL语句会怎么执行呢?

    a. 根据(name,age)联合索引查询所有满足名称以“张”开头的索引,然后回表查询出相应的全行数据,然后再筛选出满足年龄小于等于10的用户数据
    b. 根据(name,age)联合索引查询所有满足名称以“张”开头的索引,然后直接再筛选出年龄小于等于10的索引,之后再回表查询全行数据

    很明显,b的查询方式回表查询的全行数据比较少,这个过程就是索引下推。

    MySQL默认启用索引下推

    最左原则
    大家可能都知道的是一个联合索引(a, b , c),如果查询条件是

    1. where a = x
    2. where a = x and b = x
    3. where b = x and c = x and a = x

    这样是能用到索引的。但是下面2种情况就不能完全使用索引:

    1. where a = x and c = x
      索引覆盖a, c列不能走索引
    2. where a = x and b > x and c = x
      索引覆盖a和b,因b列是范围查询,因此c列不能走索引

    IN 在 where 中,也属于准确查询,不会使后面索引失效。
    遇到范围查询(>、<、between、like )就会停止匹配。

    联合索引怎么存储:把主键ID(3)的值替换成功联合索引的值(“张三”,30),叶子节点存放主键ID值。

    总结

    MySQL的索引还是比较简单的,很多都是概念性问题比较简单。掌握了B+树的索引格式基本其他问题都迎刃而解了。

    最后给大家推荐一个学习数据结构的好网站:数据结构

    展开全文
  • 文章目录索引什么是索引使用场景常见的索引哈希索引自适应哈希索引B+树索引全文索引索引的使用 索引 什么是索引 在数据库中,表、数据、索引之间的关系就类似于书籍、书籍内容、书籍目录。 倘若不使用索引,则MySQL...
  • 哈希一种非常重要的数据结构, 很多学习编程的人一直搞不懂哈希表到底如何实现的. 在这一章节中, 我们就一点点来实现一个自己的哈希表. 通过实现来理解哈希表背后的原理和它的优势. 一. 认识哈希表 我们还像...
  • 索引是什么 ’ 索引是一种特殊的文件,包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引,并指定索引的类型,各类索引有各自的数据结构实现 2.索引的效果 (1).加快查找的效率 (2).拖慢数据插入,...
  • 该系列博客索引目录:数据结构与算法—前端JavaScript学习 前面, 我们使用了大量的篇幅来解析哈希表的理论知识. 现在, 我们进入代码的实施阶段, 但是实施之前, 先来深入一个比较重要的话题: 哈希函数. 一. 哈希...
  • 什么不是哈希? hash速度远快于B+树,但是hash存在几个比较关键的问题: hash只能精确定位到一条数据,只能用=或者in,不能实现比较操作大于小于。 hash不好排序。 hash不能用部分索引。 为什么不是二叉树?...
  • 数据结构哈希

    2019-04-09 13:59:34
    哈希表就是一种以 键-值(key-indexed) 存储数据结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,...
  • !! @哈希表的实际应用 1,Sql中的索引,就是通过哈希表实现的。加大了数据存储空间,但查询速度快了很多!...@什么是哈希表? 1,google搜索到的头条:  散列表(也叫哈希表),根据关键码值直接...
  • 数据结构——哈希

    2017-12-06 10:27:13
    很多人避而不谈,虽然知道经常用到,很多语言的内置数据结构像python中的字典,java中的HashMap,都是基于哈希表实现。但哈希表究竟是啥? 哈希是什么? 散列(hashing)是电脑科学中一种对资料的处理方法,通过某种...
  • 哈希是什么哈希的核心是什么

    千次阅读 2018-02-26 00:51:33
    前两天接到阿里面试官的电话,问了我一个问题,哈希的核心...电脑科学中一种对资料的处理方法,通过某种特定的函数、算法将要检索的项与用来检索的索引关联起来,生成一种便于搜索的数据结构。 实际上通俗的说法...
  • 数据结构-哈希

    2019-05-02 16:43:20
    什么是哈希表 将元素转换为索引 将元素转换为索引的函数叫作哈希函数 f(ch)=ch-‘a’,接下来在哈希表上进行操作即可 这种转换一一对应的转换,将“键”转换为“索引” 其中字符串、浮点数、日期都可以做键,需要...
  • 在工作的时候,使用到了索引,就往下多看了一点,想知道索引使用的是什么算法,发现有BTree索引,哈希索引,全文索引,由于本人浅薄,不敢妄自定论,特此转载一前辈的。 原文地址:MySQL索引背后的数据结构及算法...
  • java数据结构哈希

    2021-03-17 16:09:30
    哈希根据关键码值(key-value)而直接进行访问的数据结构,它通过把关键码值映射到表的一个位置来访问记录,以加快查找的速度 直接来说数组就是一张哈希表 我们可以通过索引值对元素进行查找 常见的三种哈希...
  • 数据结构哈希

    2020-12-10 17:25:38
    前言介绍 在前面的文章中,先后学习了线性表、数组、字符串和树,并着分析它们对于数据的增删改查操作对于数据处理他们彼此各有千秋,例如 线性表中的栈和队列对增删有严格要求,它们会更关注...一、什么是哈希表?
  • 哈希一种根据关键码去寻找值的数据映射结构,该结构通过把关键码映射的位置去寻找存放值的地方。 哈希表充分体现了算法设计领域的经典思想:空间换时间。哈希时间和空间之间的平衡。其中的哈希函数最重要...
  • 二、索引的类型三、索引的类型的详解3.1、MySQL提供多种索引类型(按照逻辑角度分)供选择3.1.1、普通索引3.1.2、唯一性索引3.1.3、主键3.1.4、...最左前缀3.1.7、空间索引3.2、索引的类型(从数据结构角度)3.2.1、B...
  • 一、索引是什么 索引是帮助MySQL高效获取数据的排好序的数据结构。 二、索引结构 2.1 HASH索引 HASH索引是基于HASH表实现,只有精准匹配索引所有列的查询才有效。 对于每一行数据,存储引擎都会对所有的索引列计算...
  • 加速查找速度的数据结构,常见的有两类: 哈希,例如HashMap,查询/插入/修改/删除的平均时间复杂度都O(1); 树,例如平衡二叉搜索树,查询/插入/修改/删除的... 确实是哈希索引更快,因为每次都只查询一条记录。
  • 索引在MySQL中也叫做“键”,存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键,...为什么不是哈希索引?为什么不是平衡二叉树?以及为什么不是B树 在这里给大家分享一下这个网站https://www.c
  • 今天学习了四种数据结构 集合 三种基本数据结构 线形结构 (qq好友与他的说说) 树形结构 (N皇后问题,dfs) 图形结构(地铁线路,微信好友之间的关系) 四种基本的数据存储结构 顺序存储结构 链式存储结构 索引存储...
  • 散列表(Hash table,也叫哈希表),根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 众所周知,为数据表增加索引会使查询速度大大提升,MySQL索引其实一种数据结构,有“哈希”和“B+树”可供用户选择。为什么只能用这两种呢?为什么不能用二叉树、平衡二叉树、红黑树等等呢? 首先,来说一下...
  • 1、哈希索引字段映射成对应的哈希码然后再存放在对应的位置,这样的话,如果我们要进行模糊查找的话,显然哈希表这种结构是不支持的,只能遍历这个表。而B+树则可以通过最左前缀原则快速找到对应的数据。 2、...
  • 哈希一种特殊的数据结构 它与数组、链表以及树等数据结构相比,有很明显的区别。 2哈希表的核心思想 数据的存储位置和数据的具体数值之间不存在任何关系 在面对查找问题时,这些数据结构必须采用逐一比较的方法...
  • 经常听到别人讲数据库就像书的目录一样,是为了提高查询效率,那么区别又是什么?   一、索引的常见模型 1. 哈希表 2. 有序数组 3. 搜索树(InnoDB采用的是N叉B+树InnoDB引擎使用的数据结构后边重点介绍) 二...
  • 索引是一种提高我们查询效率的数据结构,大家肯定很熟悉,在日常数据库优化工作中经常会接触到。 今天说一说索引的底层结构。 【索引结构】 MySQL 索引一般是哈希表或 B+ 树,常用的 InnoDB 引擎默认使用的是 B...
  • 哈希表有称为散列表,一种空间换结构的数据结构。为每个数据加入键元素,通过键进行检索。 哈希表的组成: 键(key):自己添加的用于检索的数据,一般为整型,也可以为其他类型; 值(value):用于存储数据的地方...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 559
精华内容 223
关键字:

哈希索引是什么数据结构

数据结构 订阅