MySQL数据库(一)索引

索引的作用是操作数据库时避免全表扫描。

索引的机制

 B Tree与B+Tree索引

B(blance) 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

    • 根节点至少有两个子节点
    • 每个节点有M-1个key,并且以升序排列
    • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
    • 其它节点至少有M/2个子节点

下图是一个M=4 阶的B树:

B tree

可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。

B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示动画:

 

B+树是对B树的一种变形树,它与B树的差异在于:

    • 有k个子结点的结点必然有k个关键码;
    • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
    • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

如下图,是一个B+树:

B Plus tree

下图是B+树的插入动画:

 

B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

B+树相对于b树的优势

  1. B+树的磁盘读写代价更低
  2. B+树的查询效率跟稳定(数据都在叶子节点中)
  3. B+树更有利于对数据库的权标扫描

 

 Hash索引

  Hash索引的缺点

  • 仅仅能满足“=”,“IN”,不能使用范围查询
  • 无法对数据的排序操作
  • 不能利用部分索引键查询
  • 不能避免表扫描
  • 遇到大量hash值相等的情况 性能低

 BitMap(位图)索引

  特点:

  • 只适用于字段为固定的几个值
  • 适用于并发较少,统计运算较多的系统
  • 目前只有oracle数据库支持

索引模块 

  密集索引和稀疏索引的区别

  • 一张表只能有一个密集索引
  • 密集索引文件中的每个索引码值都对应一个索引值
  • 稀疏索引文件只为索引码的某些值建立索引项

MySql数据库有两种存储引擎:InnoDB(默认)和MyISAM

对于InnoDB:

  • 有且只有一一个密集索引
  • 若有一个主键被定义,则该主键作为密集索引
  • 若没有主键被定义,则该表的第一个唯一非空索引作为密集索引
  • 若不满足以上条件,InnoDB内部会生成一个隐藏主键
  • 非主键索引的存储的是 相关键位和其对应的主键值,查找是要经过两次查找。

对于MyISAM:

  • MyISAM的主键索引与非主键索引存储机制相同

  • MyISAM的索引与数据是分开存储的

面试题-->最左匹配原则:

  •   1、查询时,MySQL会一直向左匹配,直到遇到范围查询(<、>、between、like)就停止匹配,比如 a=3 and b=4 and c>5 and d=6,

       如果建立(a、b、c、d)顺序的索引,d是用不到索引的,如果建立(a、b、d)的索引,则都可以用到。a、b、d的顺序可以任意调整。

      2、=和in可以乱序,比如a=1 and b=2 and c=3 建立(a、b、c)索引可以任意顺序。

曹永达

发表评论 取消回复