来自 澳门威尼斯人注册网站 2019-12-28 03:08 的文章
当前位置: 澳门威尼斯人平台 > 澳门威尼斯人注册网站 > 正文

数据库索引与b+树

1、B+树基本概念

原因就是为了减少磁盘io次数,因为b+树所有最终的子节点都能在叶子节点里找见,
所以非叶子节点只需要存`索引范围和指向下一级索引(或者叶子节点)的地址` 就行了,
不需要存整行的数据,所以占用空间非常小,直到找到叶子节点才加载进来整行的数据。

B树非叶子节点也会存数据,所以不适合mysql(以后研究下mongo为啥用b树 再补充)

数据库索引详解

mysql 索引技巧,mysql索引

索引是快速搜索的关键。MySQL索引的建立对于MySQL的高效运行是很重要的。下面介绍几种常见的MySQL索引类型。

在数据库表中,对字段建立索引可以大大提高查询速度。假如我们创建了一个 mytable表:

CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL  );   我们随机向里面插入了10000条记录,其中有一条:5555, admin。

在查找username="admin"的记录 SELECT * FROM mytable WHERE username='admin';时,如果在username上已经建立了索引,MySQL无须任何扫描,即准确可找到该记录。相反,MySQL会扫描所有记录,即要查询10000条记录。

索引分单列索引和组合索引。单列索引,即一个索引只包含单个列,一个表可以有多个单列索引,但这不是组合索引。组合索引,即一个索包含多个列。

MySQL索引类型包括:

(1)普通索引

这是最基本的索引,它没有任何限制。它有以下几种创建方式:

◆创建索引

CREATE INDEX indexName ON mytable(username(length)); 如果是CHAR,VARCHAR类型,length可以小于字段实际长度;如果是BLOB和TEXT类型,必须指定 length,下同。

◆修改表结构

ALTER mytable ADD INDEX [indexName] ON (username(length)) ◆创建表的时候直接指定

CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL,   INDEX [indexName] (username(length))   );  删除索引的语法:

DROP INDEX [indexName] ON mytable;

(2)唯一索引

它与前面的普通索引类似,不同的就是:索引列的值必须唯一,但允许有空值。如果是组合索引,则列值的组合必须唯一。它有以下几种创建方式:

◆创建索引

CREATE UNIQUE INDEX indexName ON mytable(username(length)) ◆修改表结构

ALTER mytable ADD UNIQUE [indexName] ON (username(length)) ◆创建表的时候直接指定

CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL,   UNIQUE [indexName] (username(length))   ); 

(3)主键索引

它是一种特殊的唯一索引,不允许有空值。一般是在建表的时候同时创建主键索引:

CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL,   PRIMARY KEY(ID)   );  当然也可以用 ALTER 命令。记住:一个表只能有一个主键。

(4)组合索引

为了形象地对比单列索引和组合索引,为表添加多个字段:

CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL,   city VARCHAR(50) NOT NULL,   age INT NOT NULL  );  为了进一步榨取MySQL的效率,就要考虑建立组合索引。就是将 name, city, age建到一个索引里:

ALTER TABLE mytable ADD INDEX name_city_age (name(10),city,age); 建表时,usernname长度为 16,这里用 10。这是因为一般情况下名字的长度不会超过10,这样会加速索引查询速度,还会减少索引文件的大小,提高INSERT的更新速度。

如果分别在 usernname,city,age上建立单列索引,让该表有3个单列索引,查询时和上述的组合索引效率也会大不一样,远远低于我们的组合索引。虽然此时有了三个索引,但MySQL只能用到其中的那个它认为似乎是最有效率的单列索引。

建立这样的组合索引,其实是相当于分别建立了下面三组组合索引:

usernname,city,age   usernname,city   usernname  为什么没有 city,age这样的组合索引呢?这是因为MySQL组合索引“最左前缀”的结果。简单的理解就是只从最左面的开始组合。并不是只要包含这三列的查询都会用到该组合索引,下面的几个SQL就会用到这个组合索引:

SELECT * FROM mytable WHREE username="admin" AND city="郑州"  SELECT * FROM mytable WHREE username="admin" 而下面几个则不会用到:

SELECT * FROM mytable WHREE age=20 AND city="郑州"  SELECT * FROM mytable WHREE city="郑州"

(5)建立索引的时机

到这里我们已经学会了建立索引,那么我们需要在什么情况下建立索引呢?一般来说,在WHERE和JOIN中出现的列需要建立索引,但也不完全如此,因为MySQL只对<,<=,=,>,>=,BETWEEN,IN,以及某些时候的LIKE才会使用索引。例如:

SELECT t.Name  FROM mytable t LEFT JOIN mytable m    ON t.Name=m.username WHERE m.age=20 AND m.city='郑州' 此时就需要对city和age建立索引,由于mytable表的userame也出现在了JOIN子句中,也有对它建立索引的必要。

刚才提到只有某些时候的LIKE才需建立索引。因为在以通配符%和_开头作查询时,MySQL不会使用索引。例如下句会使用索引:

SELECT * FROM mytable WHERE username like'admin%' 而下句就不会使用:

SELECT * FROM mytable WHEREt Name like'%admin' 因此,在使用LIKE时应注意以上的区别。

(6)索引的不足之处

上面都在说使用索引的好处,但过多的使用索引将会造成滥用。因此索引也会有它的缺点:

◆虽然索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行INSERT、UPDATE和DELETE。因为更新表时,MySQL不仅要保存数据,还要保存一下索引文件。

◆建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重,但如果你在一个大表上创建了多种组合索引,索引文件的会膨胀很快。

索引只是提高效率的一个因素,如果你的MySQL有大数据量的表,就需要花时间研究建立最优秀的索引,或优化查询语句。

(7)使用索引的注意事项

使用索引时,有以下一些技巧和注意事项:

◆索引不会包含有NULL值的列

只要列中包含有NULL值都将不会被包含在索引中,复合索引中只要有一列含有NULL值,那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为NULL。

◆使用短索引

对串列进行索引,如果可能应该指定一个前缀长度。例如,如果有一个CHAR(255)的列,如果在前10个或20个字符内,多数值是惟一的,那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。

澳门威尼斯人注册网站,◆索引列排序

MySQL查询只使用一个索引,因此如果where子句中已经使用了索引的话,那么order by中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作;尽量不要包含多个列的排序,如果需要最好给这些列创建复合索引。

◆like语句操作

一般情况下不鼓励使用like操作,如果非使用不可,如何使用也是一个问题。like “%aaa%” 不会使用索引而like “aaa%”可以使用索引。

◆不要在列上进行运算

select * from users where YEAR(adddate)<2007; 将在每个行上进行运算,这将导致索引失效而进行全表扫描,因此我们可以改成

select * from users where adddate<‘2007-01-01’; 

◆不使用NOT IN和<>操作

以上,就对其中MySQL索引类型进行了介绍。

索引技巧,mysql索引 索引是快速搜索的关键。MySQL索引的建立对于MySQL的高效运行是很重要的。下面介绍几种常见的MySQL索引类型。 在数...

  B+树的语言定义比较复杂,简单的说是为磁盘存取设计的平衡二叉树

B+树适合作为数据库的基础结构,完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问(随机访问即给出任意一个地址,要求返回这个地址存储的数据)但是容量较小。而硬盘的随机访问要经过机械动作(1磁头移动 2盘片转动),访问效率比内存低几个数量级,但是硬盘容量较大。典型的数据库容量大大超过可用内存大小,这就决定了在B+树中检索一条数据很可能要借助几次磁盘IO操作来完成。如下图所示:通常向下读取一个节点的动作可能会是一次磁盘IO操作,不过非叶节点通常会在初始阶段载入内存以加快访问速度。同时为提高在节点间横向遍历速度,真实数据库中可能会将图中蓝色的CPU计算/内存读取优化成二叉搜索树(InnoDB中的page directory机制)。

索引

当我们在设计数据库的时候,对表的一些属性有时会加上索引,但索引为什么能提高检索速率呢?是不是用了索引就一定可以提高效率呢?不同索引之间有什么区别呢?搞懂这些问题是灵活运用索引的必备条件。接下来,我们将一 一进行讨论。

澳门威尼斯人注册网站 1

澳门威尼斯人注册网站 2

一.索引的本质

索引也分为不同的种类,而且也有不同的分类方法,比较常用的是普通索引和聚集索引。

  网上经典图,黄色p1 p2 p3代表指针,蓝色的代表磁盘,里面包含数据项,第一层17,35,p1就代表小于17的,p2就代表17-35之间的,p3就代表大于35的,可是需要注意的是,第三层才是真实的数据,17、35都不是真实数据,只是用来划分数据的!

image

1.普通索引

其实对某字段建立了索引就相当于是对该字段新建立了一个表,这个表里的元素是安照这个字段有序排列。这样有什么好处呢?好处就在于如果我们select的时候要搜索该字段,那就会在这个索引表中先查找,因为索引表是有序的,所以在检索该字段的时候就是二分搜索,速度自然会比在原表上快,然后如果我只需要这一个字段的话,查询就可以结束了,但如果还需要除索引字段的其他字段的话,那么就会根据这个索引表的字段对应到主表中,然后再获取。
看了上面讲的,是不是感觉有点迷茫?下面看一下图就会清晰很多。
澳门威尼斯人注册网站 3
(图片来源于百度)
大家可以看到这里我们以Col2建立索引之后右边有一颗二叉树,可能大家会问不是说好了是一张表吗,怎么又是二叉树了,好吧表本身就是一种树形的数据结构存储,虽然实际上很少会选取二叉树,但此处方便讲解。可以看到Col2单独的一棵树,然后每一个节点对过来是一条记录,如果我们执行 select Col2 from tablename where Col2=34;那么直接在右边的树中二叉搜索,找到了就可以返回了。如果我们执行 select * from tablename where Col2=34;那么可以看到需要的不仅仅是Col2这一个字段,那么还是先在二叉树中查找,然后找到了之后对应到主表中,然后返回整条记录。

2、为什么使用B+树

真实数据库中的B+树应该是非常扁平的,可以通过向表中顺序插入足够数据的方式来验证InnoDB中的B+树到底有多扁平。我们通过如下图的CREATE语句建立一个只有简单字段的测试表,然后不断添加数据来填充这个表。通过下图的统计数据(来源见参考文献1)可以分析出几个直观的结论,这几个结论宏观的展现了数据库里B+树的尺度。

1.索引的数据结构

通过上面的图我们可以看到,索引的本质其实就是新建了一张表,而表本质上的数据结构就是树形结构,所以索引也是树形结构。但实际运用中并没有谁用红黑树,avl树这种数据结构,一般是b+树,接下来给大家大致介绍一下b+树的构成。
澳门威尼斯人注册网站 4
(图片来源于百度)
b+树在构建时和我们之前提到的二三树很像,只是有一些改进,b+树的非叶子节点不包含value的信息,也就是说非叶子结点只起到一个导航的作用,所有的value放在了叶子结点里,这样由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。通常会将b+树进行优化,增加顺序访问指针。
澳门威尼斯人注册网站 5
(图片来源于百度0)
在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。
可以看到b+树对于表的存储是一种很方便的数据结构。那么为什么不用红黑树呢,因为数据量大的时候,会导致这种二叉树深度太深,io次数会很多,层数很少的b+树可以有效降低io次数。

  B+树有什么好处我们非要使用它呢?那就先要来看看mysql的索引

1 每个叶子节点存储了468行数据,每个非叶子节点存储了大约1200个键值,这是一棵平衡的1200路搜索树!

聚集索引

聚集索引和普通索引是不一样的,聚集索引是指数据库表行中数据的物理顺序与键值的逻辑(索引)顺序相同。一个表只能有一个聚集索引,因为一个表的物理顺序只有一种情况。意思就是说上面的普通索引我们可以看到是另建了一个表,然后当查询到了索引没有覆盖到的字段的时候是将这个字段映射到了主表中然后进行查询的。而聚集索引建立后主表本身就会按照这个索引的结构来存储,意思就是说主表直接就按这个来存了。这也是为什么聚集索引一定是唯一的原因,因为一张表中只能有一种存储方式。

 

2 对于一个22.1G容量的表,也只需要高度为3的B+树就能存储了,这个容量大概能满足很多应用的需要了。如果把高度增大到4,则B+树的存储容量立刻增大到25.9T之巨!

聚集索引与普通索引

两种索引谁更快呢?这当然是没有悬念的,聚集索引更快咯,因为普通索引查到没有覆盖的字段的时候需要向主表中映射过去,然后再获取,而聚集索引因为其本身就包含了所有数据,所以一次就好~

  2.1mysql索引

3 对于一个22.1G容量的表,B+树的高度是3,如果要把非叶节点全部加载到内存也只需要少于18.8M的内存(如何得出的这个结论?因为对于高度为2的树,1203个叶子节点也只需要18.8M空间,而22.1G从良表的高度是3,非叶节点1204个。同时我们假设叶子节点的尺寸是大于非叶节点的,因为叶子节点存储了行数据而非叶节点只有键和少量数据。),只使用如此少的内存就可以保证只需要一次磁盘IO操作就检索出所需的数据,效率是非常之高的。

主键与聚集索引

在我们新建一个表时,如果没有定义主键,那么表格的数据是顺序线性存储的,在定义的主键之后,因为主键默认有索引,并且在很多平台上默认是聚集索引,所以在主键定义的时候就会把整个表变为一个树形结构(如果主键是聚集索引),但要知道的是主键不一定是聚集索引,也可以是普通索引,只是很多平台默认为聚集,不要盲目划等号。

    试想一下在mysql中有200万条数据,在没有建立索引的情况下,会全部进行扫描读取,这个时间消耗是非常恐怖的,而对于大型一点的网站来说,达到这个数据量很容易,不可能这样去设计

澳门威尼斯人注册网站 6

索引的利弊

那么索引既然这么快是不是越多越好呢?不存在的,因为索引本身是一个数据表,那么在插入或删除的时候就涉及到了索引表的改变,b+树的插入删除涉及到很多节点操作,或许会消耗很多时间。所以我们对于常改变的字段不宜建索引,而对于改动较少的字段就很合适,在设计表的时候我们要灵活选取,才能高效。

    在我们创建数据库表的时候,大家都知道一个东西叫做主键,一般来讲数据库会自动在主键上创建索引,这叫做主键索引,来看看索引的分类吧

image

    a.主键索引:int优于varchar

    b.普通索引(INDEX):最基本的索引,没有限制,加速查找

    c.唯一索引(UNUQUE):听名字就知道,要求所有类的值是唯一的,但是允许有空值

    d.组合索引:

本文由澳门威尼斯人平台发布于澳门威尼斯人注册网站,转载请注明出处:数据库索引与b+树

关键词: