MySQL索引算法原理解析

原文出处:MySql索引算法原理解析

B-tree

B-tree,B是balance,一般用于数据库的索引。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。而B+tree是B-tree的一个变种,大名鼎鼎的MySQL就普遍使用B+tree实现其索引结构。

索引的优点

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引的形式存储在磁盘上。这样的话,索引查找的过程中就要产生磁盘I/O消耗,相对内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为数据库索引的优劣程度的重要指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
为了达到这个目的,磁盘按需读取,要求每次预读的长度一般为页的整数倍。而且数据库系统将一个页的大小设定为等于一个页,这样每个节点只需要一次I/O就可以完全载入

B-tree特性

  1. 树中每个节点至多有m个孩子;
  2. 除根结点和叶子节点外,其他每个节点至少有ceil(m/2)个孩子;
  3. 若根结点不是叶子节点,则至少有两个孩子;
  4. 所有叶子节点都出现在同一层,叶子节点不包含任何关键信息;

B-tree

示例

插入(insert)操作:插入一个元素时,首先判断在B-tree中是否存在,如果不存在,即在叶子节点处结束,然后在叶子节点处插入新的元素,如果空间满了,没有足够的空间插入新的元素,则将该节点进行“分裂”,将左右两半的关键字元素分开,中间元素上移到父节点中,如此递归,如果到根结点仍需上移,则新增加一层。
删除(delete)操作:首先查找B-tree中需要删除的元素,如果该元素在B-tree中存在,则将该元素在其节点中删除,如果删除该元素后,判断是否有孩子节点,若有,上移最近元素,递归到根结点。

SQL语句——alter用法

文章来自
SQL语句中ALTER的用法

The ALTER TABLE command allows you to add, modify, or drop a column from a existing table.

Adding column(s) to a table

Syntax #1

To add a column to an existing table, the ALTER TABLE syntax is:

1
ALTER TABLE table_name ADD column_name column_defination;

For example:

1
ALTER TABLE supplier ADD supplier_name varchar(50);

This will add a column called supplier_name to the supplier table.

Syntax #2

To add multiple columns to an existing table, the ALTER TABLE syntax is:

1
ALTER TABLE table_name ADD(
    column_1 column_1-defination,
    column_2 column_2-defination
);

For example:

1
ALTER TABLE supplier ADD(
    supplier_name varchar(50),
    city varchar(50)
);

This will add two columns(supplier_name, city) to the supplier table.

Modifying column(s) in a table

数据库概念——数据模型

数据模型的概念

在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据和信息。
通俗的讲数据模型就是现实世界的模拟
数据模型应满足如下要求:

  1. 能比较真实的模拟现实世界;
  2. 容易为人所理解;
  3. 便于在计算机上实现。

数据模型的分类

1.概念模型

概念模型也称为信息模型,是按用户的观点来对数据和信息建模,用于对数据库的设计。

2.逻辑模型

逻辑模型主要包括网状模型、层次模型、关系模型、面向对象模型等,按计算机系统的观点对数据建模,用于DBMS实现。

3.物理模型

物理模型是对数据最底层的抽象,描述数据在系统内部的表示方法和存取方法,在磁盘盒磁带上的存储方式和存取方式。

客观世界中的抽象过程

  1. 现实世界到概念模型
  2. 概念模型到逻辑模型

数据模型的组成成分

  1. 数据结构:描述数据库的组成对象,以及对象之间的联系(建表、DDL),是对系统静态特性的描述;
  2. 数据操作:对数据库中各种对象的实例允许执行的操作及有关的操作规则(DML),是对系统动态特性的描述;
  3. 完整性约束:一套完整性规则的集合。

关系数据模型的优缺点

1.优点

建立在严格的数据概念的基础上;概念单一;关系模型的存取路径对用户透明。

2.缺点

存取路径对用户透明导致了查询效率往往不如非关系数据模型;
为提高性能,必须对查询优化,增加了开发DBMS的难度。

数据库基本概念

四个基本概念

数据

数据是数据数据库中存储的基本对象,数据的定义:描述事物的符号记录。数据的种类:文本、图形、图像等。数据与其语义是不可分的。

数据库

数据库(database,简称DB)是长期在计算机内、有组织的、可共享的大量数据的集合。

数据库管理系统

位于用户和操作系统之间的一层数据管理软件,是一个基础软件,是一个大型复杂的软件系统。科学的组织和存储数据、高效的获取和维护数据。
数据库管理系统(DBMS)的主要功能:

  1. 数据定义功能(DDL);
  2. 数据的组织、存储和管理;
  3. 数据操纵功能(DML);
  4. 数据库的事务管理和运行管理;
  5. 数据库的建立和维护功能;
  6. 其他(DBMS与其他软件的系统的通信、两个DBMS系统的数据交换、异构数据库的互访和互操作)。

数据库系统

在计算机系统中引入数据库后的系统构成数据库系统。
数据库系统的构成:

  1. 数据库
  2. 数据库管理系统(及其开发工具)
  3. 应用系统
  4. 数据库管理员

数据库系统的特点

  1. 数据结构化;
  2. 数据的共享性高、冗余度低、易扩充;
  3. 数据独立性高;
  4. 数据由DBMS统一管理和控制。

数据独立性

  1. 物理独立性:指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的。当数据的物理存储改变了,应用程序不用改变。
  2. 逻辑独立性:指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结构改变了,用户程序也可以不变。
  3. 数据独立性是有DBMS的二级映射功能保证的

DBMS提供的数据控制功能

  1. 数据的安全性保护;
  2. 数据的完整心检查;
  3. 并发控制;
  4. 数据库恢复。

数据库并发控制

当多个用户同时并发的存取数据库时可能产生多个事务同时存取同一数据的情况。如果对并发操作不加控制就可能破坏数据的一致性。
并发调度的核心问题:

  1. 对并发操作进行正确的调度,有效控制;
  2. 在保证一致性的前提下最大限度地提高并发度。
    不同事务中各个步骤的执行顺序必须以某种方式进行规范,控制这些步骤的功能由DBMS的调度器部件完成。保证并发执行的事务能保持一致性的整个过程称为并发控制

事务调度

DBMS在处理用户提交事务时的策略,即事务调度。调度是一个或者多个事务的操作按时间排列的一个序列。表示事务在指令系统中执行的时间顺序。

串行调度

如果一个调度的动作顺序排列,顺序执行,没有混合,那么称这一调度为串行调度。

并行调度

如果一个调度的动作是事务之间可以相互混合,那么这一调度为并行调度。

事务调度的要求

  1. 包含所有事务的操作指令;
  2. 一个事务中指令的顺序保持不变;
  3. (串行调度)对于n个事务的事务组,可以有n!个有效调度;
  4. (并行调度)来自不同事务的指令可以交叉执行;
  5. (并行调度)当并行调度等价于某个串行调度时,则称它是正确的。

并行VS串行

  1. 并行可能破坏数据库的一致性;
  2. 串行效率较低;
  3. 因为一个事务由不同的步骤组成的,所涉及的系统资源也不同,所以可以并发执行。并行充分发挥了系统的性能;
  4. 串行会导致难以预测的时延,并行会减少平均响应时间。

并发操作事务一致性

并发操作带来数据不一致性

  1. 丢失修改:两个事务同时修改同一数据,一个事务提交破坏了另外一个事务的提交的结果(覆盖了);
  2. 不可重复读:一个事务读取一个数据后,这个数据被另外一个事务更新,导致无法再次显现前一次读取的结果;
  3. 读“脏”数据:一个事务对数据执行了更新操作,另一个事务读取了更新后的数据,而因为某种原因撤销了更新操作,使另一个事务读到了“脏”数据,或者读取到了某个事务的中间结果。

数据不一致性原因以及方法

  1. 原因:产生三类不一致性的主要原因是并发操作破坏了事务的隔离性
  2. 并发控制就是要用正确的方式调度并发操作,使一个事务的执行不受其他事务的干扰,从而避免造成数据的不一致性;
  3. 并发控制的主要技术是封锁、时间戳和有效确认。

浅谈数据库优化

作为一名后端开发人员,数据库优化是迟早要面临的问题。数据库优化对性能的提升有时是十倍甚至上百倍的量级。下面我就自己的了解对数据库优化进行一下总结分析。

如何构造一个合适的数据库结构

一个合适的数据库结构对整个项目都是至关重要的,建表时首要的就是要遵循范式要求,一般至少要满足第三范式。对于各个范式的含义,下面我做一下简单的回忆。

1NF

第一范式,简单来说就是列不可分,每一列的值都是唯一的,而不是一个集合。而所谓的不可分是一个相对的概念,比如同样的一个列’time’在不同的情况下的要求是不一样的,有的时候要求一个精确的时间到秒,而有的时候要求年份就可以了。所以我们不能用年份的标准去衡量精确到秒,而说其不满足第一范式。

2NF

第二范式,简单来说就是消除了非主属性对码的部分函数依赖。为什么要消除这种依赖呢?首先我举一个例子。

1
SNo     CNo     SName     CName    Credit

上面关系的primary key 是(SNo, CNo)共同组成的,其他属性都依赖于主关键字,但是SName并非完全依赖于主码,还依赖于主属性SNo,这就导致了数据冗余、更新异常、插入异常、删除异常。

3NF

第三范式,简单来说就是消除了非主属性对码的传递函数依赖。我还是举一个例子

1
SNo     DNo     DName

主键是SNo,而属性DName对主键是传递函数依赖,DNo依赖于SNo,并且DName依赖于DNo,这样DName就传递函数依赖于主键SNo。
不满足3NF的数据结构,可以将表拆分,使其满足3NF,这样跟合理一些。

如何构造一个合适查询语句

想达到相同的结果,有多种不同的查询策略。比如连接和查询顺序的不同,可能使查询效率有很大的差别。
在关系代数运算表达式中的一个很简单的原则,即先做选择后做连接,这种顺序上的不同,会使执行效率有戏剧性的改变。
在数据库查询过程中,系统也会相应的根据数据库结构构造出一个能最小化查询执行代价的查询计划。系统对查询所做的优化一方面出现在关系代数级,即系统尝试找出一个与给定的表达式等价但执行起来更为有效的表达式。另一方面是对于处理查询选择一个详细的策略,比如统计信息、选择可用的特定索引。
虽然数据库可以为用户选择一个合适高效的查询策略,但是也不能把所有的优化工作交给数据库管理系统来做,系统的优化是有一定局限的,况且系统这种优化本身也是一种消耗。

如何创建一个合适的索引

数据库索引是对数据库表中一个或多个列的值进行排序的结构。例如这样一个查询

1
select * from table1 where id =10000;

如果没有索引,必须要遍历整个表,直到id等于10000的这一行被找到为止,有了索引(必须是id这一列上建立的索引),即可在索引中查找。由于索引是经过某种算法优化过的,因而查找的次数要少得多。可见索引是用来定位的。
通常情况下建立索引是加快查询速度的有效手段。但索引不是万能的,靠索引不一定能实现对查询效率的提高。因此在建立索引时恰到好处比较关键。
选择索引存取方法的一般规则:

  1. 如果一个(或一组)属性经常在查询条件中出现,则要考虑在这个(或这组)属性上建立索引(或组合索引);
  2. 如果一个属性经常作为最大值和最小值等聚集函数的参数,则考虑在这个属性上建立索引;
  3. 如果一个(或一组)属性经常在连接操作的连接条件中出现则考虑这个(或这组)属性上建立索引(或组合索引。

关系上定义的索引数过多会带来较多的额外开销

  1. 维护索引的开销;
  2. 查找索引的开销。

数据库索引包括聚簇索引和非聚簇索引。为提高某个属性(或属性组)的查询速度,把这个或者这些属性(成为聚簇码)上具有相同值的元组几种存放在连续的物理块成为聚簇。
聚簇的用途:

  1. 大大提高了按聚簇码查询的效率;
  2. 节省存储空间。

聚簇的局限性:

  1. 建立聚簇只能提高某些特定应用的性能;
  2. 建立与维护聚簇开销很大。

HASH存取方法的选择

当一个关系满足下列条件时,可以选择HASH存取方法:

  1. 改关系的属性主要出现在等值连接条件中或者主要出现在相等比较选择条件中;
  2. 该关系的大小预知,而且不变或者该关系大小可变但所选用的DBMS提供了动态的HASH存取方法。