找到
18
篇与
数据库
相关的结果
-
MySQL索引完全解读 索引这个词，相信大多数人已经相当熟悉了。不过为了文章的完整性，这里再啰嗦一下。索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。 索引最形象的比喻就是图书的目录了。 注意这里的大量，数据量大了索引才显得有意义，如果我想要在[1,2,3,4]中找到4这个数据，直接对全数据检索也很快，没有必要费力气建索引再去查找。 索引在mysql数据库中分三类：1. B+树索引 2. Hash索引 3. 全文索引 我们今天要介绍的是工作开发中最常接触到innodb存储引擎中的的B+树索引。 2.二查找叉树、平衡二叉树、B树、B+树 要介绍B+树索引，就不得不提二叉查找树，平衡二叉树和B树这三种数据结构。B+树就是从他们仨演化来的。 2.1 二叉查找树 首先，让我们先看一张图  从图中可以看到，我们为user表（用户信息表）建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。键对应user表中的id，数据对应user表中的行数据。二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。 顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。如果我们需要查找id=12的用户信息，利用我们创建的二叉查找树索引，查找流程如下： 1. 将根节点作为当前节点，把12与当前节点的键值10比较，12大于10，接下来我们把当前节点>的右子节点作为当前节点。 2. 继续把12和当前节点的键值13比较，发现12小于13，把当前节点的左子节点作为当前节点。 3. 把12和当前节点的键值12对比，12等于12，满足条件，我们从当前节点中取出data，即id=1>2,name=xm。 利用二叉查找树我们只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要6次才能找到。 2.2 平衡二叉树 上面我们讲解了利用二叉查找树可以快速的找到数据。但是，如果上面的二叉查找树是这样的构造：  这个时候可以看到我们的二叉查找树变成了一个链表。如果我们需要查找id=17的用户信息，我们需要查找7次，也就相当于全表扫描了。 导致这个现象的原因其实是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。 为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度不能超过1。 下面是平衡二叉树和非平衡二叉树的对比：  由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。 2.3 B树 因为内存的易失性。一般情况下，我们都会选择将user表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。 另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。 如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。 如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？可以想象到二叉树的节点将会非常多，高度也会及其高，我们查找数据时也会进行很多次磁盘IO，我们查找数据的效率将会极低！  为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的B树。B树（Balance Tree）即为平衡树的意思，下图即是一颗B树。  注意：– 图中的p节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。 – 图中的每个节点称为页，页就是我们上面说的磁盘块，在mysql中数据读取的基本单位都是页，所以我们这里叫做页更符合mysql中索引的底层数据结构。 从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。 基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下： 1. 先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3。 2. 将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。 3. 将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)。 注意： – B树的构造是有一些规定的，但这不是本文的关注点，有兴趣的同学可以令行了解。 – B树也是平衡的，当增加或删除数据而导致B树不平衡时，也是需要进行节点调整的。 2.4 B+树 B+树是对B树的进一步优化。让我们先来看下B+树的结构图：  根据上图我们来看下B+树和B树有什么不同。 1. B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。 2. 因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。有心的读者可能还发现上图B+树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。其实上面的B树我们也可以对各个节点加上链表。其实这些不是它们之前的区别，是因为在mysql的innodb存储引擎中，索引就是这样存储的。也就是说上图中的B+树索引就是innodb中B+树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。 通过上图可以看到，在innodb中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。 MyISAM中的B+树索引实现与innodb中的略有不同。在MyISAM中，B+树索引的叶子节点并不存储数据，而是存储数据的文件地址。 3.聚集索引与非聚集索引 3.1 什么是聚集索引，什么是非聚集索引 在上节介绍B+树索引的时候，我们提到了图中的索引其实是聚集索引的实现方式。那什么是聚集索引呢？ 在MySQL中，B+树索引按照存储方式的不同分为聚集索引和非聚集索引。这里我们着重介绍innodb中的聚集索引和非聚集索引。 1. 聚集索引（聚簇索引）：以innodb作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。这是因为innodb是把数据存放在B+树中的，而B+树的键值就是主键，在B+树的叶子节点中，存储了表中所有的数据。这种以主键作为B+树索引的键值而构建的B+树索引，我们称之为聚集索引。 2. 非聚集索引（非聚簇索引）：以主键以外的列值作为键值构建的B+树索引，我们称之为非聚集索引。非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。明白了聚集索引和非聚集索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。 3.2 利用聚集索引和非聚集索引查找数据 前面我们讲解B+树索引的时候并没有去说怎么在B+树中进行数据的查找，主要就是因为还没有引出聚集索引和非聚集索引的概念。下面我们通过讲解如何通过聚集索引以及非聚集索引查找数据表中数据的方式介绍一下B+树索引查找数据方法。 3.2.1 利用聚集索引查找数据  还是这张B+树索引图，现在我们应该知道这就是聚集索引，表中的数据存储在其中。现在假设我们要查找id>=18并且id=18 and id =18 and id
-
深入分析事务的隔离级别 本文详细介绍四种事务隔离级别，并通过举例的方式说明不同的级别能解决什么样的读现象。并且介绍了在关系型数据库中不同的隔离级别的实现原理。 在DBMS中，事务保证了一个操作序列可以全部都执行或者全部都不执行（原子性），从一个状态转变到另外一个状态（一致性）。由于事务满足久性。所以一旦事务被提交之后，数据就能够被持久化下来，又因为事务是满足隔离性的，所以，当多个事务同时处理同一个数据的时候，多个事务直接是互不影响的，所以，在多个事务并发操作的过程中，如果控制不好隔离级别，就有可能产生脏读、不可重复读或者幻读等读现象。 在数据库事务的ACID四个属性中，隔离性是一个最常放松的一个。可以在数据操作过程中利用数据库的锁机制或者多版本并发控制机制获取更高的隔离等级。但是，随着数据库隔离级别的提高，数据的并发能力也会有所下降。所以，如何在并发性和隔离性之间做一个很好的权衡就成了一个至关重要的问题。 在软件开发中，几乎每类这样的问题都会有多种最佳实践来供我们参考，很多DBMS定义了多个不同的“事务隔离等级”来控制锁的程度和并发能力。 ANSI/ISO SQL定义的标准隔离级别有四种，从高到底依次为：可序列化(Serializable)、可重复读(Repeatable reads)、提交读(Read committed)、未提交读(Read uncommitted)。 下面将依次介绍这四种事务隔离级别的概念、用法以及解决了哪些问题（读现象） 未提交读(Read uncommitted) 未提交读(READ UNCOMMITTED)是最低的隔离级别。通过名字我们就可以知道，在这种事务隔离级别下，一个事务可以读到另外一个事务未提交的数据。 未提交读的数据库锁情况（实现原理） 事务在读数据的时候并未对数据加锁。 务在修改数据的时候只对数据增加行级共享锁。 现象： 事务1读取某行记录时，事务2也能对这行记录进行读取、更新（因为事务一并未对数据增加任何锁） 当事务2对该记录进行更新时，事务1再次读取该记录，能读到事务2对该记录的修改版本（因为事务二只增加了共享读锁，事务一可以再增加共享读锁读取数据），即使该修改尚未被提交。 事务1更新某行记录时，事务2不能对这行记录做更新，直到事务1结束。（因为事务一对数据增加了共享读锁，事务二不能增加排他写锁进行数据的修改） 举例 下面还是借用我在数据库的读现象浅析一文中举的例子来说明在未提交读的隔离级别中两个事务之间的隔离情况。 事务一 事务二 /* Query 1 */SELECT age FROM users WHERE id = 1;/* will read 20 */ /* Query 2 */UPDATE users SET age = 21 WHERE id = 1;/* No commit here */ /* Query 1 */SELECT age FROM users WHERE id = 1;/* will read 21 */ ROLLBACK;/* lock-based DIRTY READ */ 事务一共查询了两次，在两次查询的过程中，事务二对数据进行了修改，并未提交（commit）。但是事务一的第二次查询查到了事务二的修改结果。在数据库的读现象浅析中我们介绍过，这种现象我们称之为脏读。 所以，未提交读会导致脏读 提交读(Read committed) 提交读(READ COMMITTED)也可以翻译成读已提交，通过名字也可以分析出，在一个事务修改数据过程中，如果事务还没提交，其他事务不能读该数据。 提交读的数据库锁情况 事务对当前被读取的数据加 行级共享锁（当读到时才加锁），一旦读完该行，立即释放该行级共享锁； 事务在更新某数据的瞬间（就是发生更新的瞬间），必须先对其加 行级排他锁，直到事务结束才释放。 现象： 事务1在读取某行记录的整个过程中，事务2都可以对该行记录进行读取（因为事务一对该行记录增加行级共享锁的情况下，事务二同样可以对该数据增加共享锁来读数据。）。 事务1读取某行的一瞬间，事务2不能修改该行数据，但是，只要事务1读取完改行数据，事务2就可以对该行数据进行修改。（事务一在读取的一瞬间会对数据增加共享锁，任何其他事务都不能对该行数据增加排他锁。但是事务一只要读完该行数据，就会释放行级共享锁，一旦锁释放，事务二就可以对数据增加排他锁并修改数据） 事务1更新某行记录时，事务2不能对这行记录做更新，直到事务1结束。（事务一在更新数据的时候，会对该行数据增加排他锁，知道事务结束才会释放锁，所以，在事务二没有提交之前，事务一都能不对数据增加共享锁进行数据的读取。所以，提交读可以解决脏读的现象） 举例 事务一 事务二 /* Query 1 */SELECT * FROM users WHERE id = 1; /* Query 2 */UPDATE users SET age = 21 WHERE id = 1;COMMIT;/* in multiversion concurrencycontrol, or lock-based READ COMMITTED */ /* Query 1 */SELECT * FROM users WHERE id = 1;COMMIT; /*lock-based REPEATABLE READ */ 在提交读隔离级别中，在事务二提交之前，事务一不能读取数据。只有在事务二提交之后，事务一才能读数据。 但是从上面的例子中我们也看到，事务一两次读取的结果并不一致，所以提交读不能解决不可重复读的读现象。 简而言之，提交读这种隔离级别保证了读到的任何数据都是提交的数据，避免了脏读(dirty reads)。但是不保证事务重新读的时候能读到相同的数据，因为在每次数据读完之后其他事务可以修改刚才读到的数据。 可重复读(Repeatable reads) 可重复读(REPEATABLE READS),由于提交读隔离级别会产生不可重复读的读现象。所以，比提交读更高一个级别的隔离级别就可以解决不可重复读的问题。这种隔离级别就叫可重复读（这名字起的是不是很任性！！） 可重复读的数据库锁情况 事务在读取某数据的瞬间（就是开始读取的瞬间），必须先对其加 行级共享锁，直到事务结束才释放； 事务在更新某数据的瞬间（就是发生更新的瞬间），必须先对其加 行级排他锁，直到事务结束才释放。 现象 事务1在读取某行记录的整个过程中，事务2都可以对该行记录进行读取（因为事务一对该行记录增加行级共享锁的情况下，事务二同样可以对该数据增加共享锁来读数据。）。 事务1在读取某行记录的整个过程中，事务2都不能修改该行数据（事务一在读取的整个过程会对数据增加共享锁，直到事务提交才会释放锁，所以整个过程中，任何其他事务都不能对该行数据增加排他锁。所以，可重复读能够解决不可重复读的读现象） 事务1更新某行记录时，事务2不能对这行记录做更新，直到事务1结束。（事务一在更新数据的时候，会对该行数据增加排他锁，知道事务结束才会释放锁，所以，在事务二没有提交之前，事务一都能不对数据增加共享锁进行数据的读取。所以，提交读可以解决脏读的现象） 举例 事务一 事务二 /* Query 1 */SELECT * FROM users WHERE id = 1;COMMIT; /* Query 2 */UPDATE users SET age = 21 WHERE id = 1;COMMIT;/* in multiversion concurrencycontrol, or lock-based READ COMMITTED */ 在上面的例子中，只有在事务一提交之后，事务二才能更改该行数据。所以，只要在事务一从开始到结束的这段时间内，无论他读取该行数据多少次，结果都是一样的。 从上面的例子中我们可以得到结论：可重复读隔离级别可以解决不可重复读的读现象。但是可重复读这种隔离级别中，还有另外一种读现象他解决不了，那就是幻读。看下面的例子： 事务一 事务二 /* Query 1 */SELECT * FROM usersWHERE age BETWEEN 10 AND 30; /* Query 2 */INSERT INTO users VALUES ( 3, 'Bob', 27 );COMMIT; /* Query 1 */SELECT * FROM usersWHERE age BETWEEN 10 AND 30; 上面的两个事务执行情况及现象如下： 1.事务一的第一次查询条件是age BETWEEN 10 AND 30;如果这是有十条记录符合条件。这时，他会给符合条件的这十条记录增加行级共享锁。任何其他事务无法更改这十条记录。 2.事务二执行一条sql语句，语句的内容是向表中插入一条数据。因为此时没有任何事务对表增加表级锁，所以，该操作可以顺利执行。 3.事务一再次执行SELECT * FROM users WHERE age BETWEEN 10 AND 30;时，结果返回的记录变成了十一条，比刚刚增加了一条，增加的这条正是事务二刚刚插入的那条。 所以，事务一的两次范围查询结果并不相同。这也就是我们提到的幻读。 可序列化(Serializable) 可序列化(Serializable)是最高的隔离级别，前面提到的所有的隔离级别都无法解决的幻读，在可序列化的隔离级别中可以解决。 我们说过，产生幻读的原因是事务一在进行范围查询的时候没有增加范围锁(range-locks：给SELECT 的查询中使用一个“WHERE”子句描述范围加锁），所以导致幻读。 可序列化的数据库锁情况 事务在读取数据时，必须先对其加 表级共享锁 ，直到事务结束才释放； 事务在更新数据时，必须先对其加 表级排他锁 ，直到事务结束才释放。 现象 事务1正在读取A表中的记录时，则事务2也能读取A表，但不能对A表做更新、新增、删除，直到事务1结束。(因为事务一对表增加了表级共享锁，其他事务只能增加共享锁读取数据，不能进行其他任何操作） 事务1正在更新A表中的记录时，则事务2不能读取A表的任意记录，更不可能对A表做更新、新增、删除，直到事务1结束。（事务一对表增加了表级排他锁，其他事务不能对表增加共享锁或排他锁，也就无法进行任何操作） 虽然可序列化解决了脏读、不可重复读、幻读等读现象。但是序列化事务会产生以下效果： 1.无法读取其它事务已修改但未提交的记录。 2.在当前事务完成之前，其它事务不能修改目前事务已读取的记录。 3.在当前事务完成之前，其它事务所插入的新记录，其索引键值不能在当前事务的任何语句所读取的索引键范围中。 四种事务隔离级别从隔离程度上越来越高，但同时在并发性上也就越来越低。之所以有这么几种隔离级别，就是为了方便开发人员在开发过程中根据业务需要选择最合适的隔离级别。 参考资料 维基百科-事务隔离 数据库隔离级别 及 其实现原理
-
再有人问你MySQL索引原理，就把这篇文章甩给他！ 本文来自作者投稿，作者：zyz1992 索引，可能让好很多人望而生畏，毕竟每次面试时候 MySQL 的索引一定是必问内容，哪怕先撇开面试，就在平常的开发中，对于 SQL 的优化也而是重中之重。 可以毫不夸张的说，系统中 SQL 的好坏，是能直接决定你系统的快慢的。但是在优化之前大家是否想过一个问题？那就是：我们优化的原则是什么？优化SQL的理论基础是什么？ 虽然说实践出真知，但是我更相信理论是支撑实践的基础，因为我们不可能毫无目的的去盲目的实践，因为这样往往事倍功半。 所以说了这么多只想告诉大家，在真正的开始索引优化之前，我们需要彻底搞明白索引的原理。这样再谈优化你将觉得更丝滑~ 1、索引的本质 索引的本质是一种排好序的数据结构。这个我相信其实大家并不陌生，因为谈到索引很多人自然而然的就会联想到字典中的目录。 没错，这样的类比是很形象的，但是如果再往深处说，恐怕很多小伙伴就有点张口结舌了，那既然你已经知道了索引的本质，那么您就已经有了看这篇文章的基础，相信读文本文的你，一定会对索引的原理有一个全新的了解。 2、索引的分类 在数据库中，索引是分很多种类的（千万不要狭隘的认为索引只有 B+ 树，那是因为我们平时使用的基本都是 MySQL）。而不同的种类很显然是为了应付不同的场合，那索引到底有那些种类呢？下面就让我们来大致的了解下。 2.1、Hash 索引 Hash 索引是比较常见的一种索引，他的单条记录查询的效率很高，时间复杂度为1。但是，Hash索引并不是最常用的数据库索引类型，尤其是我们常用的Mysql Innodb引擎就是不支持hash索引的。主要有以下原因： Hash索引适合精确查找，但是范围查找不适合 因为存储引擎都会为每一行计算一个hash码，hash码都是比较小的，并且不同键值行的hash码通常是不一样的，hash索引中存储的就是Hash码，hash 码彼此之间是没有规律的，且 Hash 操作并不能保证顺序性，所以值相近的两个数据，Hash值相差很远，被分到不同的桶中。这就是为什么hash索引只能进行全职匹配的查询，因为只有这样，hash码才能够匹配到数据。 对于 hash 索引，小伙伴们只需要了解到这里就可以了。 2.2、二叉树 另外，常见的索引使用的数据结构是树结构，首先我们来介绍下最经典的二叉树。 先来介绍下二叉树的特点： 二叉树的时间复杂度为 O(n) 一个节点只能有两个子节点。即度不超过2 左子节点 小于 本节点，右子节点 大于 本节点 首先来看一下二叉树的样子 但是在极端情况下会出现链化的情况，即节点一直在某一边增加。如下图 二叉树中，有一种特殊的结构——平衡二叉树，平衡二叉树的特点： 根节点会随着数据的改变而变更 数据量越多，遍历次数越多，IO次数就越多，就越慢（磁盘的IO由树高决定） 2.4、B树（二三树） 了解了二叉树之后，可以进一步谈一下什么是B树了。B 树大概是这样子的： 从B树的结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。 而每页的存储空间是有限的，如果 data 比较大，会导致每个节点的 key 存储的较少，当数据量较大的时候，同样会导致B树很深，从而增加了磁盘 IO 的次数，进而影响查询效率。 好了，说到这里，常见的索引的种类也说完了，上面的内容仅仅是作为一个铺垫，下面我们正式开始 MySQL 的 B+ 树。 2.5、B+树 MySQL 中最常用的索引的数据结构是 B+ 树，他有以下特点： 在 B+ 树中，所有数据记录节点都是按照键值的大小存放在同一层的叶子节点上，而非叶子结点只存储key的信息，这样可以大大减少每个节点的存储的key的数量，降低B+ 树的高度 B+ 树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。 B+ 树的层级更少：相较于 B 树 B+ 每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快 B+ 树查询速度更稳定：B+ 所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定; B+ 树天然具备排序功能：B+ 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。 B+ 树全节点遍历更快：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。 好了说了这么多的 B+ 树的特点，我们来张图看看 B+ 树到底长什么样子（如果看不懂，也没有关系，下文会一步一步解释说明的） 上面的数据页就是实际存放数据页的地方，且数据页之间是通过双向链表进行连接的，好了到这里我们就将各个索引的类型快速了解了下，下面我们就开始正式B+树的分析。 3、主键目录 我们将上图中的数据页拿出来再细化下，就成了下面的这张图 我们都知道 MySQL 在存储数据的时候是以数据页为最小单位的，且数据在数据页中的存储是连续的，数据页中的数据是按照主键排序的（没有主键是由 MySQL自己维护的 ROW_ID 来排序的），数据页和数据页之间是通过双向链表来关联的，数据与数据时间是通过单向链表来关联的。 也就是说有一个在每个数据页中，他必然就有一个最小的主键，然后每个数据页的页号和最小的主键会组成一个主键目录（就像上图中的左边部分），假设现在要查找主键为 2 的数据，通过二分查找法最后确定下主键为 2 的记录在数据页 1 中，此时就会定位到数据页 1 接着再去定位主键为 2 的记录，我们先知道大致的流程，细节先不要深究，先从宏观看结构原理，再到微观看实现原理。 刚刚上面是说的其实可以理解为是主键索引，主键索引也是最简单的最基础的索引。这个时候大家应该知道为什么你建立了主键查询就能变快了吧？ 4、索引页 但是现在假设有很多很多的是数据页，那是不是对应的主键目录会很大很大呢？ 那假设有1000万条记录、5000万条记录呢？是不是就算是二分法查找，其效率也依旧是很低的，所以为了解决这种问题 MySQL 又设计出了一种新的存储结构—索引页。例如有下面这样情况， 假设上面的主键目录中的记录是非常非常多的，此时上面的结构是演变成这样子的，MySQL 会将里面的记录拆分到不同的索引页中，也就是下面这样子的 索引页中记录的是每页数据页的页号和该数据页中最小的主键的记录，也就是说最小主键和数据页号不是单纯的维护在主键目录中了，而是演变成了索引页，索引页和数据页类似，一张不够存就分裂到下一张。 假如现在要查找 id=20 的这条记录，咦？那我应该到哪个索引页中查找该条记录呢？所以这个时候肯定是需要去维护索引页的。 没错，MySQL 也是这么设计的，也就是说 MySQL 同时也设计出了用于维护索引页的数据结构，其实也还叫索引页，只不过他们是在不同的层级，类似下面这样子的： 也就是说维护索引页的索引页是在真正存储记录和数据页的索引页的上一层，现在如果你想查找 id=20 的这条记录，那就是从最上层的索引页开始查找，通过二分法查找，很快就能够定位到 id=20 s这条记录是在索引页 2 上，然后到就索引页 2 上面查找，接着就是和之前一样了（注意，索引页中的记录也是通过单向链表连接的），根据各个最小的主键能够定位到 id=20 是在数据页5上，假设数据页5是这样子的 那这个时候你是不是能够想明白数据是怎么定位的了呢？ 5、索引页的分层 好，既然你已经知道到索引页太多会往上一层扩散，那现在假设上一层的索引页记录也太多了，那该怎么办？很简单，继续分裂，再往上一层继续，不废话，我来画图帮助大家理解 我看明白了，你看明白了吗？我们来模拟一个查找的过程，假设你要查找 37 这条记录，说实话我根本不知道这条记录在哪里。好，现在我们就来模拟 MySQL 的查找过程，首先从最顶层的索引页开始查找，因为 id=37，因此定位到了索引页16，然后到索引页 16 中继续查找，此时同样能够定位到 id=37 在索引页 3 中，然后继续查找，最终能够定位到数据实在数据页 8 中，假设数据页 8 是这样子的 是不是很完美？如果非要我把上面的图画完整，那….小弟义不容辞（图太大了，索引页中数据的链表结构就不画出来了） 这个时候机智的你是不是已经发现了什么小秘密？他是不是很像一颗二叉树？实际上这就是一颗 B+ 树的结构，这也是数据在磁盘中真正存储的物理结构。B+树的特性是什么呢？B+树，也是二叉搜索树的一种，但是他的数据仅仅存储在叶子节点（在这里就是数据页），像这种索引页+数据页组成的组成的B+树就是聚簇索引(这句话很重要)。 聚簇索引是 MySQL 基于主键索引结构创建的 6、非主键索引 但是现在问题又来了，既然这里强调的是主键索引，那我们平时开发中除了主键索引其他的索引也用的不少，这时候该怎么办？假设你现在对name、age建立索引。现在回顾下主键索引，是不是在插入数据的时候基于主键的顺序去维护一个 B+ 树的？ 而实际上非主键索引其原理是一样的，MySQL 都是去维护一颗 B+ 树，说白了，你建立多少个索引，MySQL 就会帮你维护多少的B+树（这下是不是也突然想明白了为什么索引不能建立太多了？以前就知道不能建立太多索引，因为索引也会占用空间，实际上这就是根本原因） 假如现在真的对name+age建立索引，那此时是存放的呢？此时 MySQL 根据会 name+age 维护一个单独的 B+ 树结构，数据依旧是存放在数据页中的，只不过是原来数据中的每条记录写的是 id=xx，现在写的是name=xx，age=xx，id=xx，不管怎么样，主键肯定会存放的，先来张图压压惊 在插入数据的时候，MySQL 首先会根据 name 进行排序，如果 name 一样，就根据联合索引中的 age 去排序，如果还一样，那么就会根据 主键 字段去排序。插入的原理就是这样子的。 此时每个数据页中的记录存放的实际是索引字段和主键字段，而其他字段是不存的（为什么不存放？一样的数据到处存放很浪费空间的，也没必要，所以才会有下面的索引优化），至于查找，原理和过程跟聚簇索引一样，这里就不再赘述，但是，下面说的内容却是至关重要的：假设现在执行这样的SQL： SELECT name FROM student WHERE name='wx' 那么此时的查询是完美的，使用到了索引且不需要回表 7.回表 是这样子的，现在要根据 name 查找到该条记录，且查询的字段（即 select 后面的查询字段）也仅仅有 name（只要是在 name,age,id 这三个字段中都可以）这个时候是能够直接获取到最终的记录的 换句话说，因为联合索引中的记录也仅仅有 name，age，id，所以在查询的如果也仅仅查询这三个字段，那么在该B+树中就能够查询到想要的结果了。 那现在假设查询的 SQL 是这样子的（我们假设 student 中还有除了name，age，id 其他的字段 ） SELECT * FROM student WHERE name='wx' 那这下子就完蛋了，因为你现在虽然根据 name 很快的定位到了该条记录，但是因为 name+age 不是聚簇索引，此时的 B+ 树的数据页中存放的仅仅是自己关联的索引和主键索引字段，并不会存其他的字段，所以这个时候其他的属性值是获取不到的，这时候该怎么办？ 这种情况下，MySQL 就需要进行回表查询了。此时 MySQL 就会根据定位到的某条记录中的 id 再次进行聚簇索引查找，也就是说会根据 id 去维护 id 的那么 B+ 树中查找。因为聚簇索引中数据页记录的是一条记录的完整的记录，这个过程就叫回表。 再强调下回表的含义：根据非主键索引查询到的结果并没有查找的字段值，此时就需要再次根据主键从聚簇索引的根节点开始查找，这样再次查找到的记录才是完成的。 最后，让我一起看下 MySQL 对于非主键索引的维护过程： 对于非主键索引（一般都是联合索引），在维护 B+ 树的时候，会根据联合索引的字段依次去判断，假设联合索引为：name + address + age，那么 MySQL 在维护该索引的 B+ 树的时候，首先会根据 name 进行排序，name 相同的话会根据第二个 address 排序，如果 address 也一样，那么就会根据 age 去排序，如果 age 也一样，那么就会根据主键字段值去排序，且对于非主键索引，MySQL 在维护 B+ 树的时候，仅仅是维护索引字段和主键字段。
-
为什么阿里巴巴禁止数据库中做多表join？ 阿里出过一个《Java开发手册》，上面有一条规约是禁止超过三张表的join。 而实际操作过程中，我们平时确实在SQL中写JOIN也比较少，两张表JOIN有的时候也有，多张表的JOIN在离线数据分析的时候很多，但是在线系统确实很少。经常有人问我为什么？ 其实最主要的原因就是join的效率比较低。 MySQL是使用了嵌套循环（Nested-Loop Join）的方式来实现关联查询的，简单点说就是要通过两层循环，用第一张表做外循环，第二张表做内循环，外循环的每一条记录跟内循环中的记录作比较，符合条件的就输出。 而具体到算法实现上主要有simple nested loop，block nested loop和index nested loop这三种。 而且这三种的效率都没有特别高。 首先，最差的算法就是simple nested loop，他的做法简单粗暴，就是全量扫描连接两张表进行数据的两两对比，所以他的复杂度可以认为是O（n^2) 好一点的算法是index nested loop，当Inner Loop的表用到字段有索引的话，可以用到索引进行查询数据，因为索引是B+树的，复杂度可以近似认为是O（nlogn） 那block nested loop这种算法，其实是引入了一个Buffer，会提前把外循环的一部分结果提前放到多个JOIN BUFFER中，然后内循环的每一行都和多个buffer中的所有数据作比较，从而减少内循环的次数。他的复杂度是O（M*N），这里的M是buffer的个数。 所以，虽然MySQL已经尽可能的在优化了，但是这几种算法复杂度都还是挺高的，这也是为什么不建议在数据库中多表JOIN的原因。随着表越多，表中的数据量越多，JOIN的效率会呈指数级下降。 如果不能通过数据库做关联查询，那么需要查询多表的数据的时候要怎么做呢？ 主要有两种做法： 1、在内存中自己做关联，即先从数据库中把数据查出来之后，我们在代码中再进行二次查询，然后再进行关联。 2、数据冗余，那就是把一些重要的数据在表中做冗余，这样就可以避免关联查询了。 其实数据冗余是互联网业务中比较常见的做法，其实本质上是软件开发中一个比较典型的方案，那就是”用空间换时间”，通过做一些数据冗余，来提升查询速度。 在互联网业务中，比较典型的就是数据量大，并发高，并且通常查询的频率要远高于写入的频率，所以适当的做一些反范式，通过做一些字段的冗余，可以提升查询性能，降低响应时长，从而提升并发度。
-
MySQL中的读锁和写锁 在数据库的锁机制中介绍过，数据的锁主要用来保证数据的一致性的，数据库的锁从锁定的粒度上可以分为表级锁、行级锁和页级锁。在我的博客中重点介绍过MySQL数据库的行级锁。这篇文章主要来介绍一下MySQL数据库中的表级锁。 本文提到的读锁和写锁都是MySQL数据库的MyISAM引擎支持的表锁的。而对于行级锁的共享读锁和互斥写锁请阅读MySQL中的共享锁与排他锁。我习惯在描述表锁的时候按照读写来区分，在表述行锁的时候按照共享和互斥来区分。其实无论是表锁还是行锁。共享锁指的就是读锁！互斥锁、排他锁、独占锁值得都是写锁。 重点知识回顾 MySQL的锁机制比较简单，其最显著的特点是不同的存储引擎支持不同的锁机制。比如，MyISAM和MEMORY存储引擎采用的是表级锁(table-level locking);BDB 存储引擎采用的是页面锁(page-level locking)，但也支持表级锁;InnoDB存储引擎既支持行级锁(row-level locking)，也支持表级锁，但默认情况下是采用行级锁。 表级锁:开销小，加锁快;不会出现死锁;锁定粒度大，发生锁冲突的概率最高，并发度最低。 行级锁:开销大，加锁慢;会出现死锁;锁定粒度最小,发生锁冲突的概率最低，并发度也最高。 页面锁:开销和加锁时间界于表锁和行锁之间;会出现死锁;锁定粒度界于表锁和行锁之间，并发度一般。 MyISAM表锁 MyISAM 存储引擎只支持表锁，MySQL 的表级锁有两种模式:表共享读锁(Table Read Lock)和表独占写锁(Table Write Lock)。 对于读操作，可以增加读锁，一旦数据表被加上读锁，其他请求可以对该表再次增加读锁，但是不能增加写锁。（当一个请求在读数据时，其他请求也可以读，但是不能写，因为一旦另外一个线程写了数据，就会导致当前线程读取到的数据不是最新的了。这就是不可重复读现象） 对于写操作，可以增加写锁，一旦数据表被加上写锁，其他请求无法在对该表增加读锁和写锁。（当一个请求在写数据时，其他请求不能执行任何操作，因为在当前事务提交之前，其他的请求无法看到本次修改的内容。这有可能产生脏读、不可重复读和幻读） 读锁和写锁都是阻塞锁。 如果t1对数据表增加了写锁，这是t2请求对数据表增加写锁，这时候t2并不会直接返回，而是会一直处于阻塞状态，直到t1释放了对表的锁，这时t2便有可能加锁成功，获取到结果。 表锁的加锁/解锁方式 MyISAM 在执行查询语句(SELECT)前,会自动给涉及的所有表加读锁,在执行更新操作 (UPDATE、DELETE、INSERT 等)前，会自动给涉及的表加写锁，这个过程并不需要用户干预，因此，用户一般不需要直接用LOCK TABLE命令给MyISAM表显式加锁。 如果用户想要显示的加锁可以使用以下命令： 锁定表：LOCK TABLES tbl_name {READ | WRITE},[ tbl_name {READ | WRITE},…] 解锁表：UNLOCK TABLES 在用 LOCK TABLES 给表显式加表锁时,必须同时取得所有涉及到表的锁。 在执行 LOCK TABLES 后，只能访问显式加锁的这些表，不能访问未加锁的表; 如果加的是读锁，那么只能执行查询操作，而不能执行更新操作。 在自动加锁的情况下也基本如此，MyISAM 总是一次获得 SQL 语句所需要的全部锁。这也正是 MyISAM 表不会出现死锁(Deadlock Free)的原因。 对表test_table增加读锁： LOCK TABLES test_table READ UNLOCK test_table 对表test_table增加写锁 LOCK TABLES test_table WRITE UNLOCK test_table 当使用 LOCK TABLES 时,不仅需要一次锁定用到的所有表,而且,同一个表在 SQL 语句中出现多少次,就要通过与 SQL 语句中相同的别名锁定多少次,否则也会出错! 比如如下SQL语句： select a.first_name,b.first_name, from actor a,actor b where a.first_name = b.first_name; 该Sql语句中，actor表以别名的方式出现了两次，分别是a,b，这时如果要在该Sql执行之前加锁就要使用以下Sql: lock table actor as a read,actor as b read; 并发插入 上文 到过 MyISAM 表的读和写是串行的,但这是就总体而言的。在一定条件下,MyISAM表也支持查询和插入操作的并发进行。 MyISAM存储引擎有一个系统变量concurrent_insert,专门用以控制其并发插入的行为,其值分别可以为0、1或2。 当concurrent_insert设置为0时,不允许并发插入。 当concurrent_insert设置为1时,如果MyISAM表中没有空洞(即表的中间没有被删除的 行),MyISAM允许在一个进程读表的同时,另一个进程从表尾插入记录。这也是MySQL 的默认设置。 当concurrent_insert设置为2时,无论MyISAM表中有没有空洞,都允许在表尾并发插入记录。 可以利用MyISAM存储引擎的并发插入特性,来解决应用中对同一表查询和插入的锁争用。 MyISAM的锁调度 前面讲过,MyISAM 存储引擎的读锁和写锁是互斥的,读写操作是串行的。那么,一个进程请求某个 MyISAM 表的读锁,同时另一个进程也请求同一表的写锁,MySQL 如何处理呢? 答案是写进程先获得锁。 不仅如此,即使读请求先到锁等待队列,写请求后到,写锁也会插到读锁请求之前!这是因为 MySQL 认为写请求一般比读请求要重要。这也正是 MyISAM 表不太适合于有大量更新操作和查询操作应用的原因,因为,大量的更新操作会造成查询操作很难获得读锁,从而可能永远阻塞。这种情况有时可能会变得非常糟糕! 幸好我们可以通过 一些设置来调节 MyISAM 的调度行为。 通过指定启动参数low-priority-updates,使MyISAM引擎默认给予读请求以优先的权利。 通过执行命令SET LOW_PRIORITY_UPDATES=1,使该连接发出的更新请求优先级降低。 通过指定INSERT、UPDATE、DELETE语句的LOW_PRIORITY属性,降低该语句的优先级。 另外,MySQL也 供了一种折中的办法来调节读写冲突,即给系统参数max_write_lock_count 设置一个合适的值,当一个表的读锁达到这个值后,MySQL就暂时将写请求的优先级降低, 给读进程一定获得锁的机会。 总结 数据库中的锁从锁定的粒度上分可以分为行级锁、页级锁和表级锁。 MySQL的MyISAM引擎支持表级锁。 表级锁分为两种：共享读锁、互斥写锁。这两种锁都是阻塞锁。 可以在读锁上增加读锁，不能在读锁上增加写锁。在写锁上不能增加写锁。 默认情况下，MySql在执行查询语句之前会加读锁，在执行更新语句之前会执行写锁。 如果想要显示的加锁/解锁的花可以使用LOCK TABLES和UNLOCK来进行。 在使用LOCK TABLES之后，在解锁之前，不能操作未加锁的表。 在加锁时，如果显示的指明是要增加读锁，那么在解锁之前，只能进行读操作，不能执行写操作。 如果一次Sql语句要操作的表以别名的方式多次出现，那么就要在加锁时都指明要加锁的表的别名。 MyISAM存储引擎有一个系统变量concurrent_insert,专门用以控制其并发插入的行为,其值分别可以为0、1或2。 由于读锁和写锁互斥，那么在调度过程中，默认情况下，MySql会本着写锁优先的原则。可以通过low-priority-updates来设置。 参考资料 《深入浅出MySQL》
