《数据库和算法知识简介.doc》由会员分享，可在线阅读，更多相关《数据库和算法知识简介.doc（27页珍藏版）》请在金锄头文库上搜索。
1、写在前面的话在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”，我个人是不太赞同这句话（因为我觉得程序不仅仅是数据结构加算法），但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性，很多东 西，如果你愿意稍稍往深处挖一点，那么扑面而来的一定是各种数据结构和算法知识。例如几乎每个程序员都要打交道的数据库，如果仅仅是用来存个数据、建建 表、建建索引、做做增删改查，那么也许觉得数据结构和这东西没什么关系。不过要是哪天心血来潮，想知道的多一点，想研究一下如何优化数据库，那么一定避免 不了研究索引的原理，如果想要真正明白索引是怎么工作的，如何合理的使用索引以优化数据库，那么就免不了
2、纠结于一堆数据结构与算法之间了。所以，如果说 “程序的核心基础 = 数据结构 + 算法”我是十分赞同的，而一个想成为高手的程序员，一定会去学习程序的核心基础。好吧，说了这么 多，其实我的意思是如果想把数据库索引学个明明白白，就必须将数据结构和算法作为切入点去学习，遗憾的是我目前还没有在网上找到从原理层面去介绍数据库索 引的资料（这里仅指在通俗资料领域没找到，不包括学术论文），倒不是说没有高水平的程序员，就只在我们公司范围内能把这一点讲透彻讲明白的数据库大牛也海 了去了，只是由于工作的忙碌和个人兴趣原因，这些大牛们没有时间或没有兴趣去写这方面的文章。由于工作的需要，我这个半桶水的程序员这段时间也
3、草草研究一 些关于MySQL数据库索引的东西，虽然对这方面的理解相比那些大牛差的太远了，不过这里我还是将这些浅薄的知识总结成文吧。摘要数据结构及算法基础 索引的本质 B-Tree和B+Tree 为什么实用B-Tree（B+Tree）MySQL索引实现 MyISAM索引实现 InnoDB索引实现索引使用策略及优化 示例数据库 最左前缀原理与相关优化 索引选择性与前缀索引 InnoDB的主键选择与插入优化后记参考文献摘要本 文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相 同，因此MySQL数据库支持多
4、种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用 MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。文章主要内容分为四个部分。第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。第三部分根据上面的理论基础，讨论MySQL中高性能使用索引的策略。数据结构及算法基础索引的本质MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干
5、，就可以得到索引的本质：索引是数据结构。我们知道，数据库查询是数据库的最主要功能之一，例如下面的SQL语句：SELECT * FROM my_table WHERE col2 = 77可以从表“my_table”中获得“col2”为“77”的数据记录。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），遍历“my_table”然后逐行匹配“col2”的值是否是“77”，这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary
6、search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。看一个例子：图1图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻
7、的记录在磁盘上也并不是一定物理 相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用 二叉查找在O(log2n)的复杂度内获取到相应数据。虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。B-Tree和B+Tree目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引，这一节先单纯
8、从数据结构角度描述它们。B-Tree为了描述B-Tree，首先定义一条数据记录为一个二元组key, data，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：1. d为大于1的一个正整数，称为B-Tree的度。 2. h为一个正整数，称为B-Tree的高度。 3. 每个非叶子节点由n-1个key和n个指针组成，其中d=n key) return BTree_Search(pointi-node); return BTree_Search(pointi+1-node);data = BTree_Search(
9、root, my_key);关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd(N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，本 文不打算完整讨论B-Tree这些内容，因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法，有兴趣的朋友可以在本文末的参考文献一栏找 到相应的资料进行阅读。B+Tree
10、B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。与B-Tree相比，B+Tree有以下不同点：1. 每个节点的指针上限为2d而不是2d+1。 2. 内节点不存储data，只存储key；叶子节点不存储指针。 图3是一个简单的B+Tree示意。图3由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。一般来说，B+Tree比B-Tree更适合实现
11、外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。带有顺序访问指针的B+Tree一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。图4如图4所示，在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高 区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点， 极大提到了区间查询效率。这一节对B-Tree和B+Tree进行了一个简单的介绍，下一节结合存储器
12、存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。为什么使用B-Tree（B+Tree）上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消 耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂 度。换句话说，索引的结构组织
13、要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索 引的效率。主存存取原理目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。图5从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。主存的存取过程如下：当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。写主存的过程类似，系统将要写入单元地址和数据分别放在地
