Hadoop 的优化与发展

Hadoop 的局限与不足

Hadoop1.0 的核心组件（仅指 MapReduce 和 HDFS，不包括 Hadoop 生态系统内的 Pig、Hive、HBase 等其他组件）主要存在以下不足。

1. 抽象层次低。需要手工编写代码来完成，有时只是为了实现一个简单的功能，也需要编写大量的代码。
2. 表达能力有限。MapReduce 把复杂分布式编程工作高度抽象到两个函数上，即 Map 和 Reduce，在降低开发人员程序开发复杂度的同时，却也带来了表达能力有限的问题，实际生产环境中的一些应用是无法用简单的 Map 和 Reduce 来完成的。
3. 开发者自己管理作业之间的依赖关系。一个作业（Job）只包含 Map 和 Reduce 两个阶段，通常的实际应用问题需要大量的作业进行协作才能顺利解决，这些作业之间往往存在复杂的依赖关系，但是 MapReduce 框架本身并没有提供相关的机制对这些依赖关系进行有效管理，只能由开发者自己管理。
4. 难以看到程序整体逻辑。用户的处理逻辑都隐藏在代码细节中，没有更高层次的抽象机制对程序整体逻辑进行设计，这就给代码理解和后期维护带来了障碍。
5. 执行迭代操作效率低。对于一些大型的机器学习、数据挖掘任务，往往需要多轮迭代才能得到结果。采用 MapReduce 实现这些算法时，每次迭代都是一次执行 Map、Reduce 任务的过程，这个过程的数据来自分布式文件系统 HDFS，本次迭代的处理结果也被存放到 HDFS 中，继续用于下一次迭代过程。反复读写 HDFS 文件中的数据，大大降低了迭代操作的效率。
6. 资源浪费。在 MapReduce 框架设计中，Reduce 任务需要等待所有 Map 任务都完成后才可以开始，造成了不必要的资源浪费。
7. 实时性差。只适用于离线批数据处理，无法支持交互式数据处理、实时数据处理。

针对 Hadoop 的改进与提升

HDFS2.0 的新特性

相对于之前的 HDFS1.0 而言，HDFS2.0 增加了 HDFS HA 和 HDFS 联邦等新特性。

HDFS HA

对于分布式文件系统 HDFS 而言，名称节点（NameNode）是系统的核心节点，存储了各类元数据信息，并负责管理文件系统的命名空间和客户端对文件的访问。但是，在 HDFS1.0 中，只存在一个名称节点，一旦这个唯一的名称节点发生故障，就会导致整个集群变得不可用，这就是常说的“单点故障问题”。虽然 HDFS1.0 中存在一个“第二名称节点（Secondary NameNode）”，但是第二名称节点并不是名称节点的备用节点，它与名称节点有着不同的职责，其主要功能是周期性地从名称节点获取命名空间镜像文件（FsImage）和修改日志（EditLog），进行合并后再发送给名称节点，替换掉原来的 FsImage，以防止日志文件 EditLog 过大，导致名称节点失败恢复时消
耗过多时间。合并后的命名空间镜像文件 FsImage 在第二名称节点中也保存一份，当名称节点失效的时候，可以使用第二名称节点中的 FsImage 进行恢复。

由于第二名称节点无法提供“热备份”功能，即在名称节点发生故障的时候，系统无法实时切换到第二名称节点立即对外提供服务，仍然需要进行停机恢复，因此 HDFS1.0 的设计是存在单点故障问题的。为了解决单点故障问题，HDFS2.0 采用了 HA（High Availability）架构。在一个典型的 HA 集群中，一般设置两个名称节点，其中一个名称节点处于“活跃（Active）”状态，另一个处于“待命（Standby）”状态。处于活跃状态的名称节点负责对外处理所有客户端的请求，而处于待命状态的名称节点则作为备用节点，保存了足够多的系统元数据，当名称节点出现故障时提供快速恢复能力。也就是说，在 HDFS HA 中，处于待命状态的名称节点提供了“热备份”，一旦活跃名称节点出现故障，就可以立即切换到待命名称节点，不会影响到系统的正常对外服务。

由于待命名称节点是活跃名称节点的“热备份”，因此活跃名称节点的状态信息必须实时同步到待命名称节点。两种名称节点的状态同步，可以借助于一个共享存储系统来实现，比如 NFS（Network File Systerm）、QJM（Quorum Jourmal Manager）或者 Zookeeper。活跃名称节点将更新数据写人到共享存储系统，待命名称节点会一直监听该系统，一旦发现有新的写人，就立即从公共存储系统中读取这些数据并加载到自己的内存中，从而保证与活跃名称节点状态完全同步。

此外，名称节点中保存了数据块（Block）到实际存储位置的映射信息，即每个数据块是由哪个数据节点存储的。当一个数据节点加入 HDFS 集群时，它会把自己所包含的数据块列表报告给名称节点，此后会通过“心跳”的方式定期执行这种告知操作，以确保名称节点的块映射是最新的。因此，为了实现故障时的快速切换，必须保证待命名称节点一直包含最新的集群中各个块的位置信息。为了做到这一点，需要给数据节点配置两个名称节点的地址（即活跃名称节点和待命名称节点），并把块的位置信息和心跳信息同时发送到这两个名称节点。为了防止出现“两个管家”现象，HA 还要保证任何时刻都只有一个名称节点处于活跃状态，否则，如果有两个名称节点处于活跃状态，HDFS 集群中出现“两个管家”，就会导致数据丢失或者其他异常，这个任务是由 Zookeeper 来实现的，Zookeeper 可以确保任意时刻只有一个名称节点提供对外服务。

HDFS 联邦

HDFS1.0 中存在的问题

HDFS1.0 采用单名称节点的设计，不仅会带来单点故障问题，还存在可扩展性、性能和隔离性等问题。在可扩展性方面，名称节点把整个 HDFS 文件系统中的元数据信息都保存在自己的内存中，HDFS1.0 中只有一个名称节点，不可以水平扩展，而单个名称节点的内存空间是有上限的，这限制了系统中数据块、文件和目录的数目。是否可以通过纵向扩展的方式（即为单个名称节点增加更多的 CPU、内存等资源）解决这个问题呢？答案是否定的。纵向扩展带来的第一个问题就是，会带来过长的系统启动时间，比如一个具有 50 GB 内存的 HDFS 启动一次大概需要消耗 30min~2h，单纯增大内存空间只会让系统启动时间变得更长。其次，当在内存空间清理时发生错误，就会导致整个 HDFS 集群宕机。

在系统整体性能方面，整个 HDFS 文件系统的性能会受限于单个名称节点的吞吐量。在隔离性方面，单个名称节点难以提供不同程序之间的隔离性，一个程序可能会影响其他运行的程序（比如一个程序消耗过多资源导致其他程序无法顺利运行）。HDFS HA 虽然提供了两个名称节点，但是在某个时刻也只会有一个名称节点处于活跃状态，另个则处于待命状态。因而，HDFS HA 在本质上还是单名称节点，只是通过“热备份”设计方式解决了单点故障问题，并没有解决可扩展性、系统性能和隔离性三个方面的问题。

HDFS 联邦的设计

HDFS 联邦可以很好地解决上述三个方面的问题。在 HDFS 联邦中，设计了多个相互独立的名称节点，使得 HDFS 的命名服务能够水平扩展，这些名称节点分别进行各自命名空间和块的管理，相互之间是联邦关系，不需要彼此协调。HDFS 联邦并不是真正的分布式设计，但是采用这种简单的“联合”设计方式，在实现和管理复杂性方面，都要远低于真正的分布式设计，而且可以快速满足需求。在兼容性方面，HDFS 联邦具有良好的向后兼容性，可以无缝地支持单名称节点架构中的配置。所以，原有针对单名称节点的部署配置，不需要作任何修改就可以继续工作。

HDFS 联邦中的名称节点提供了命名空间和块管理功能。在 HDFS 联邦中，所有名称节点会共享底层的数据节点存储资源。每个数据节点要向集群中所有的名称节点注册，并周期性地向名称节点发送“心跳”和块信息，报告自已的状态，同时也会处理来自名称节点的指令。

HDFS1.0 只有一个命名空间，这个命名空间使用底层数据节点全部的块。与 HDFS1.0 不同的是，HDFS 联邦拥有多个独立的命名空间，其中，每一个命名空间管理属于自己的一组块，这些属于同一个命名空间的块构成一个“块池”（Block Pool）。每个数据节点会为多个块池提供块的存储。可以看出，数据节点是一个物理概念，而块池则属于逻辑概念，一个块池是一组块的逻辑集合，块池中的各个块实际上是存储在各个不同的数据节点中的。因此，HDFS 联邦中的一个名称节点失效，也不会影响到与它相关的数据节点继续为其他名称节点提供服务。

HDFS 联邦的访问方式

对于 HDFS 联邦中的多个命名空间，可以采用客户端挂载表（Client Side Mount Table）方式进行数据共享和访问。每个阴影三角形代表一个独立的命名空间，上方空白三角形表示从客户方向去访问下面子命名空间。客户可以访问不同的挂载点来访问不同的子命名空间。这就是 HDFS 联邦中命名空间管理的基本原理，即把各个命名空间挂载到全局“挂载表”（Mount-table）中，实现数据全局共享；同样地，命名空间挂载到个人的挂载表中，就成为应用程序可见的命名空间。

HDFS 联邦相对于 HDFS1.0 的优势

采用 HDFS 联邦的设计方式，可解决单名称节点存在的以下 3 个问题。

1. HDFS 集群可扩展性。多个名称节点各自分管一部分目录，使得个集群可以扩展到更多节点，不再像 HDFS1.0 中那样由于内存的限制制约文件存储数目。
2. 性能更高效。多个名称节点管理不同的数据，且同时对外提供服务，将为用户提供更高的读写吞吐率。
3. 良好的隔离性。用户可根据需要将不同业务数据交由不同名称节点管理，这样不同业务之间影响很小。

需要注意的是，HDFS 联邦并不能解决单点故障问题，也就是说，每个名称节点都存在单点故障问题，需要为每个名称节点部署一个后备名称节点，以应对名称节点宕机后对业务产生的影响。

新一代资源管理调度框架 YARN

MapReduce1.0 的缺陷

MapReduce1.0 采用 Master/Slave 架构设计，包括二个 JobTracker 和若干个 TaskTracker，前者负责作业的调度和资源的管理，后者负责执行 JobTracker 指派的具体任务。这种架构设计具有一些很难克服的缺陷，具体如下。

1. 存在单点故障。由 JobTracker 负责所有 MapReduce 作业的调度，而系统中只有一个 JobTracker，因此会存在单点故障问题，即这个唯一的 JobTracker 出现故障就会导致系统不可用。
2. JobTracker“大包大揽”导致任务过重。JobTracker 既要负责作业的调度和失败恢复，又要负责资源管理分配。执行过多的任务，需要消耗大量的资源，例如，当存在非常多的 MapReduce 任务时，JobTracker 需要巨大的内存开销，这也潜在地增加了 JobTracker 失败的风险。正因如此，业内普遍总结出 MapReduce1.0 支持主机数目的上限为 4000 个。
3. 容易出现内存溢出。在 TaskTracker 端，资源的分配并不考虑 CPU、内存的实际使用情况，而只是根据 MapReduce 任务的个数来分配资源，当两个具有较大内存消耗的任务被分配到同一个 TaskTracker 上时，很容易发生内存溢出的情况。
4. 资源划分不合理。资源（CPU、内存）被强制等量划分成多个“槽”（Slot），槽又被进一步划分为 Map 槽和 Reduce 槽两种，分别供 Map 任务和 Reduce 任务使用，彼此之间不能使用分配给对方的槽，也就是说，当 Map 任务已经用完 Map 槽时，即使系统中还有大量剩余的 Reduce 槽，也不能拿来运行 Map 任务，反之亦然。这就意味着，当系统中只存在单一 Map 任务或 Reduce 任务时，会造成资源的浪费。

YARN 设计思路

为了克服 MapReduce1.0 版本的缺陷，Hadoop2.0 以后的版本对其核心子项目 MapReduce1.0 的体系结构进行了重新设计，生成了 MapReduce2.0 和 YARN（Yet Another Resource Negotiator）。YARN 架构设计基本思路就是“放权”，即不让 JobTracker 这一个组件承担过多的功能，把原 JobTracker 三大功能（资源管理、任务调度和任务监控）进行拆分，分别交给不同的新组件去处理。重新设计后得到的 YARN 包括 ResourceManager 、ApplicationMaster 和 NodeManager，其中，由 ResourceManager 负责资源管理，由 ApplicationMaster 负责任务调度和监控，由 NodeManager 负责执行原 TaskTracker 的任务。通过这种“放权”的设计，大大降低了 JobTracker 的负担，提升了系统运行的效率和稳定性。

在 Hadoop1.0 中，其核心子项目 MapReduce1.0 既是一个计算框架，也是一个资源管理调度框架。到了 Hadoop2.0 以后，MapReduce1.0 中的资源管理调度功能被单独分离出来形成了 YARN，它是一个纯粹的资源管理调度框架，而不是一个计算框架；而被剥离了资源管理调度功能的 MapReduce 框架就变成了 MapReduce2.0，它是运行在 YARN 之上的一个纯粹的计算框架，不再自己负责资源调度管理服务，而是由 YARN 为其提供资源管理调度服务。

YARN 体系架构

YARN 体系结构中包含了三个组件：ResourceManager、ApplicationMaster 和 NodeManager。

ResourceManager（RM）是一个全局的资源管理器，负责整个系统的资源管理和分配，主要包括两个组件，即调度器（Scheduler）和应用程序管理器（Applications Manager）。调度器主要负责资源管理和分配，不再负责跟踪和监控应用程序的执行状态，也不负责执行失败恢复，因为这些任务都已经交给 ApplicationMaster 组件来负责。调度器接收来自 ApplicationMaster 的应用程序资源请求，并根据容量、队列等限制条件（如每个队列分配一定的资源，最多执行一定数量的作业等)，把集群中的资源以“容器”的形式分配给提出申请的应用程序，容器的选择通常会考虑应用程序所要处理的数据的位置，进行就近选择，从而实现“计算向数据靠拢”。在 MapReduce1.0 中，资源分配的单位是“槽”，而在 YARN 中是以容器（Container）作为动态资源分配单位，每个容器中都封装了一定数量的 CPU、内存、磁盘等资源，从而限定每个应用程序可以使用的资源量。同时，在 YARN 中调度器被设计成是一个可插拔的组件，YARN 不仅自身提供了许多种直接可用的调度器，也允许用户根据自己的需求重新设计调度器。应用程序管理器负责系统中所有应用程序的管理工作，主要包括应用程序提交、与调度器协商资源以启动 ApplicationMaster、 监控 ApplicationMaster 运行状态并在失败时重新启动等。

在 Hadoop 平台上，用户的应用程序是以作业（Job）的形式提交的，然后一个作业会被分解成多个任务（包括 Map 任务和 Reduce 任务）进行分布式执行。ResourceManager 接收用户提交的作业，按照作业的上下文信息以及从 NodeManager 收集来的容器状态信息，启动调度过程，为用户作业启动一个 ApplicationMaster。

ApplicationMaster 的主要功能是:

1. 当用户作业提交时，ApplicationMaster 与 ResourceManager 协商获取资源，ResourceManager 会以容器的形式为 ApplicationMaster 分配资源；
2. 把获得的资源进步分配给内部的各个任务（Map 任务或 Reduce 任务），实现资源的“二次分配”；
3. 与 NodeManager 保持交互通信进行应用程序的启动、运行、监控和停止，监控申请到的资源的使用情况，对所有任务的执行进度和状态进行监控，并在任务发生失败时执行失败恢复（即重新申请资源重启任务）；
4. 定时向 ResourceManager 发送“心跳”消息，报告资源的使用情况和应用的进度信息；
5. 当作业完成时，ApplicationMaster 向 ResourceManager 注销容器，执行周期完成。

NodeManager 是驻留在一个 YARN 集群中的每个节点上的代理，主要负责容器生命周期管理，监控每个容器的资源（CPU、内存等）使用情况，跟踪节点健康状况，并以“心跳”的方式与 ResourceManager 保持通信，向 ResourceManager 汇报作业的资源使用情况和每个容器的运行状态，同时，它还要接收来自 ApplicationMaster 的启动/停止容器的各种请求。需要说明的是，NodeManager 主要负责管理抽象的容器，只处理与容器相关的事情，而不具体负责每个任务（Map 任务或 Reduce 任务）自身状态的管理，因为这些管理工作是由 ApplicationMaster 完成的，ApplicationMaster 会通过不断与 NodeManager 通信来掌握各个任务的执行状态。

在集群部署方面，YARN 的各个组件是和 Hadoop 集群中的其他组件进行统一部署的。YARN 的 ResourceManager 组件和 HDFS 的名称节点（NameNode）部署在一个节点上，YARN 的 ApplicationMaster 及 NodeManager 是和 HDFS 的数据节点（DataNode）部署在一-起的。YARN 中的容器代表了 CPU、内存、网络等计算资源，它也是和 HDFS 的数据节点一起的。

YARN 工作流程

在 YARN 框架中执行一个 MapReduce 程序时，从提交到完成需要经历如下8个步骤。

1. 用户编写客户端应用程序，向 YARN 提交应用程序，提交的内容包括 ApplicationMaster 程序、启动 ApplicationMaster 的命令、用户程序等。
2. YARN 中的 ResourceManager 负责接收和处理来自客户端的请求。接到客户端应用程序请求后，ResourceManager 里面的调度器会为应用程序分配一个容器。同时，ResourceManager 的应用程序管理器会与该容器所在的 NodeManager 通信，为该应用程序在该容器中启动一个 ApplicationMaster。
3. ApplicationMaster 被创建后会首先向 ResourceManager 注册，从而使得用户可以通过 ResourceManager 来直接查看应用程序的运行状态。接下来的步骤4~7是具体的应用程序执行步骤。
4. ApplicationMaster 采用轮询的方式通过 RPC 协议向 ResourceManager 申请资源。
5. ResourceManager 以“容器”的形式向提出申请的 ApplicationMaster 分配资源，一旦 ApplicationMaster 申请到资源后，就会与该容器所在的 NodeManager 进行通信，要求它启动任务。
6. 当 ApplicationMaster 要求容器启动任务时，它会为任务设置好运行环境（包括环境变量、JAR 包、二进制程序等），然后将任务启动命令写到一个脚本中，最后通过在容器中运行该脚本来启动任务。
7. 各个任务通过某个 RPC 协议向 ApplicationMaster 汇报自己的状态和进度，让 AplicationMater 可以随时掌握各个任务的运行状态，从而可以在任务失败时重新启动任务。
8. 应用程序运行完成后，ApplicationMaster 向 ResourceManager 的应用程序管理器注销并关闭自己。若 ApplicationMaster 因故失败，ResourceManager 中的应用程序管理器会监测到失败的情形，然后将其重新启动，直到所有的任务执行完毕。

概述

数据仓库概念

数据仓库的体系结构通常包含四个层次：数据源、数据存储和管理、数据服务、数据应用，具体如下：

• 数据源：是数据仓库的数据来源，包括了外部数据、现有业务系统和文档资料等；
• 数据集成：完成数据的抽取、清洗、转换和加载任务，数据源中的数据采用 ETL 工具以固定的周期加载到数据仓库中；
• 数据存储和管理：这一层次主要涉及对数据的存储和管理，包括数据仓库、数据集市、数据仓库检测、运行与维护工具和元数据管理等；
• 数据服务：为前端工具和应用提供数据服务，可以直接从数据仓库中获取数据供前端应用使用，也可以通过 OLAP（Online Analytical Processing）服务器为前端应用提供更加复杂的数据服务。OLAP 服务器提供了不同聚集粒度的多维数据集合，使得应用不需要直接访问数据仓库中的底层细节数据，大大减少了数据计算量，提高了查询响应速度。OLAP 服务器还支持针对多维数据集的上钻、下探、切片、切块和旋转等操作，增强了多维数据分析能力；
• 数据应用：这一层次直接面向最终用户，包括数据查询工具、自由报表工具、数据分析工具、数据挖掘工具和各类应用系统。

Hive 简介

Hive 是一个构建于 Hadoop 顶层的数据仓库工具，依赖 HDFS 来存储数据，依赖 MapReduce 来处理数据。Hive 定义了简单的类似 SQL 的查询语言 HiveQL，它与大部分 SQL 语法兼容，但是，并不完全支持 SQL 标准，比如，HiveSQL 不支持更新操作，也不支持索引和事务，它的子查询和连接操作也存在很多局限。

Hive 与 Hadoop 生态系统中其他组件的关系

HDFS 作为高可靠的底层存储，用来存储海量数据；MapReduce 对这些海量数据进行批处理，实现高性能计算；Hive 架构在 MapReduce、HDFS 之上，其自身并不存储和处理数据，需要分别借助于 HDFS 和 MapReduce 实现数据的存储和处理，用 HiveQL 语句编写的处理逻辑，最终都要转化为 MapReduce 任务来运行；Pig 可以作为 Hive 的替代工具，是一种数据流语言和运行环境，适合用于在 Hadoop 平台上查询半结构化数据集，常用于 ETL 过程的一部分，即将外部数据装载到 Hadoop 集群中，然后转换为用户需要的数据格式；HBase 是一个面向列的、分布式的、可伸缩的数据库，它可以提供数据的实时访问功能，而 Hive 只能处理静态数据，主要是 BI 报表数据，就设计初衷而言，在 Hadoop 上设计 Hive，是为了减少复杂 MapReduce 应用程序的编写工作，在 Hadoop 上设计 HBase 则是为了实现对数据的实时访问，所以，HBase 与 Hive 的功能是互补的，它实现了 Hive 不能提供的功能。

Hive 与传统数据库的对比

Hive 系统架构

Hive 主要由以下三个模块组成：用户接口模块、驱动模块以及元数据存储模块。

用户接口模块包括 CLI、HWI、JDBC、ODBC、Thrift Server 等，用来实现外部应用对 Hive 的访问。

• CLI 是 Hive 自带的一个命令行界面
• HWI 是 Hive 的一个简单网页界面
• JDBC、ODBC 以及 Thrift Server 可以向用户提供进行编程访问的接口
  • Thrift Server 是基于 Thrift 软件框架开发的，它提供 Hive 的 RPC 通信接口

驱动模块（Driver）包括编译器、优化器、执行器等，负责把 HiveSQL 语句转换成一系列 MapReduce 作业，所有命令和查询都会进入到驱动模块，通过该模块对输入进行解析编译，对计算过程进行优化，然后按照指定的步骤执行。

元数据存储模块（Metastore）是一个独立的关系型数据库，通常是与 MySQL 数据库连接后创建的一个 MySQL 实例，也可以是 Hive 自带的 derby 数据库实例。元数据存储模块中主要保存表模式和其他系统元数据，如表的名称、表的列及其属性、表的分区及其属性、表的属性、表中数据所在位置信息等。

Hive 工作原理

Hive 可以快速实现简单的 MapReduce 统计，主要是通过自身组件把 HiveQL 语句转换成 MapReduce 任务来实现的。

SQL 语句转换成 MapReduce 作业的基本原理

用 MapReduce 实现连接操作

假设参与连接（join）的两个表分别为用户表 User 和订单表 Order，User 表有两个属性，即 uid 和 name，Order 表也有两个属性，即 uid 和 orderid，它们的连接键为公共属性 uid。这里对两个表执行连接操作，得到用户的订单号与用户名的对应关系，具体的 SQL 语句命令如下：select name, orderid from user u join order o on u.uid=o.uid;

首先，在 Map 阶段， User 表以 uid 为键（key），以 name 和表的标记位（这里 User 的标记位记为 1）为值（value）进行 Map 操作，把表中记录转化成生成一系列键值对的形式。同样地，Order 表以 uid 为键，以 orderid 和表的标记位（这里表 Order 的标记位记为 2）为值进行 Map 操作，把表中 记录转化成生成一系列键值对的形式。比如，User 表中记录 (1,Lily) 转化为键值对 (1,<1,Lily>)，其中，括号中的第一个“1”是 uid 的值，第二个“1”是表 User 的标记位，用来标识这个键值对来自 User 表；再比如，Order 表中记录 (1,101) 转化为键值对 (1,<2,101>)，其中，“2”是表 Order 的标记位，用来标识这个键值对来自 Order 表。

接着，在 Shuffle 阶段，把 User 表和 Order 表生成的键值对按键值进行哈希，然后传送给对应的 Reduce 机器执行，比如键值对 (1,<1,Lily>)、(1,<2,101>) 和 (1,<2,102>) 传送到同一台 Reduce 机器上，键值对 (2,<1,Tom>) 和 (2,<2,103>) 传送到另一台 Reduce 机器上。当 Reduce 机器接收这些键值对时，还需要按表的标记位对这些键值对进行排序，以优化连接操作。

最后，在 Reduce 阶段，对同一台 Reduce 机器上的键值对，根据“值”（value）中的表标记位，对来自 User 和 Order 这两个表的数据进行笛卡尔积连接操作，以生成最终的连接结果。比如，键值对 (1,<1,Lily>) 与键值对 (1,<2,101>) 和 (1,<2,102>) 的连接结果分别为 (Lily ,101>) 和 (Lily, 102)，键值对 (2,<1,Tom>) 和键值对 (2,<2,103>) 的连接结果为 (Tom, 103)。

用 MapReduce 实现分组操作

假设分数表 Score 具有两个属性，即 rank（排名）和 level（级别），这里存在一个分组（Group By）操作，其功能是把表 Score 的不同片段按照 rank 和 level 的组合值进行合并，计算不同 rank 和 level 的组合值分别有几条记录。具体的 SQL 语句命令如下：select rank, level ,count(*) as value from score group by rank, level;

首先，在 Map 阶段，对表 Score 进行 Map 操作，生成一系列键值对，对于每个键值对，其键为 <rank,level>，值为“拥有该 <rank,value> 组合值的记录的条数”。比如，Score 表的第一片段中有两条记录 (A,1)，所以，记录 (A,1) 转化为键值对 (<A,1>,2)，Score 表的第二片段中只有一条记录 (A,1)，所以，记录 (A,1) 转化为键值对 (<A,1>,1)。

接着，在 Shuffle 阶段，对 Score 表生成的键值对，按照“键”的值进行哈希，然后根据哈希结果传送给对应的 Reduce 机器去执行，比如键值 对 (<A,1>,2) 和 (<A,1>,1) 传送到同一台 Reduce 机器上，键值对 (<B,2>,1) 传送到另一台 Reduce 机器上。然后，Reduce 机器对接收到的这些键值对，按“键”的值进行排序。

最后，在 Reduce 阶段，对于 Reduce 机器上的这些键值对，把具有相同键的所有键值对的“值”进行累加，生成分组的最终结果，比如，在同一台 Reduce 机器上的键值对 (<A,1>,2) 和 (<A,1>,1>) Reduce 后的输出结果为 (<A,1>,3)，(<B,2>,1) 的 Reduce 后的输出结果为 (<B,2>,1)。

Hive 中 SQL 查询转换成 MapReduce 作业的过程

当用户向 Hive 输入一段命令或查询（即 HiveQL 语句）时，Hive 需要与 Hadoop 交互工作来完成该操作。该命令或查询首先进入到驱动模块，由驱动模块中的编译器进行解析编译，并由优化器对该操作进行优化计算，然后交给执行器去执行。执行器通常的任务是启动一个或多个 MapReduce 任务，有时也不需要启动 MapReduce 任务，比如，执行包含 * 的操作时（如 select * from 表），就是全表扫描，选择所有的属性和所有的元组，不存在投影和选择操作，因此，不需要执行 Map 和 Reduce 操作。

在 Hive 中，用户通过命令行 CLI 或其他 Hive 访问工具，向 Hive 输入一段命令或查询以后，SQL 查询被 Hive 自动转化为 MapReduce 作业，具体步骤如下：

1. 由 Hive 驱动模块中的编译器——Antlr 语言识别工具，对用户输入的 SQL 语言进行词法和语法解析，将 SQL 语句转化为抽象语法树（AST Tree）的形式；
2. 对该抽象语法树进行遍历，进一步转化成 QueryBlock 查询单元。因为抽象语法树的结构仍很复杂，不方便直接翻译为 MapReduce 算法程序，所以，Hive 把抽象语法树进一步转化为 QueryBlock，其中，QueryBlock 是一条最基本的 SQL 语法组成单元，包括输入源、计算过程和输出三个部分；
3. 再对 QueryBlock 进行遍历，生成 OperatorTree（操作树）。其中，OperatorTree 由很多逻辑操作符组成，如 TableScanOperator、SelectOperator、FilterOperator、JoinOperator、 GroupByOperator 和 ReduceSinkOperator 等。这些逻辑操作符可以在 Map 阶段和 Reduce 阶 段完成某一特定操作；
4. 通过 Hive 驱动模块中的逻辑优化器对 OperatorTree 进行优化，变换 OperatorTree 的形式，合并多余的操作符，从而减少 MapReduce 任务数量以及 Shuffle 阶段的数据量；
5. 对优化后的 OperatorTree 进行遍历，根据 OperatorTree 中的逻辑操作符生成需要执行的 MapReduce 任务；
6. 启动 Hive 驱动模块中的物理优化器，对生成的 MapReduce 任务进行优化，生成最终的 MapReduce 任务执行计划；
7. 最后由 Hive 驱动模块中的执行器，对最终的 MapReduce 任务进行执行输出。

需要说明的是，Hive 驱动模块中的执行器执行最终的 MapReduce 任务时，Hive 本身是不会生成 MapReduce 算法程序的，它需要通过一个表示“Job 执行计划”的 XML 文件，来驱动执行内置的、原生的 Mapper 和 Reducer 模块。Hive 通过和 JobTracker 通信来初始化 MapReduce 任务，而不需要直接部署在 JobTracker 所在的管理节点上执行。通常在大型集群上，会有专门的网关机来部署 Hive 工具。这些网关机的作用主要是远程操作和管理节点上的 JobTracker 通信来执行任务。Hive 要处理的数据文件通常存储在 HDFS 上，HDFS 由名称节点（NameNode）来管理。

Hive HA 基本原理

Hive 的功能十分强大，可以支持采用 SQL 方式查询 Hadoop 平台上的数据，但是，在实际应用中，Hive 也暴露出不稳定的问题，在极少数情况下，甚至会出现端口不响应或者进程丢失的问题。Hive HA（High Availability）的出现，就是为了解决这类问题。

在 Hive HA 中，在 Hadoop 集群上构建的数据仓库是由多个 Hive 实例进行管理的，这些 Hive 实例被纳入到一个资源池中，并由 HAProxy 提供一个统一的对外接口。客户端的查询请求首先访问 HAProxy，由 HAProxy 对访问请求进行转发。HAProxy 收到请求后，会轮询资源池里可用的 Hive 实例，执行逻辑可用性测试，如果某个 Hive 实例逻辑可用，就会把客户端的访问请求转发到该 Hive 实例上，如果该 Hive 实例逻辑不可用，就把它放入黑名单，并继续从资源池中取出下一个 Hive 实例进行逻辑可用性测试。对于黑名单中的 Hive 实例，HiveHA 会每隔一段时间进行统一处理，首先尝试重启该 Hive 实例，如果重启成功，就再次把它放入到资源池中。由于采用 HAProxy 提供统一的对外访问接口，因此，对于程序开发人员来说，可以把它认为是一台超强“Hive”。

概述

模型简介

在 MapReduce 中，一个存储在分布式文件系统中的大规模数据集会被切分成许多独立的小数据块，这些小数据块可以被多个 Map 任务并行处理。MapReduce 框架会为每个 Map 任务输入一个数据子集，Map 任务生成的结果会继续作为 Reduce 任务的输人，最终由 Reduce 任务输出最后结果，并写入分布式文件系统。

特别注意：适合用 MapReduce 来传护理的数据集需要满足一个前提条件：待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。

MapReduce 设计的一个理念就是“计算向数据靠拢”，而不是“数据向计算靠拢”，因为移动数据需要大量的网络传输开销，尤其是在大规模数据环境下，这种开销尤为惊人，所以，移动计算要比移动数据更加经济。本着这个理念，在一个集群中，只要有可能，MapReduce 框架就会将 Map 程序就近地在 HDFS 数据所在的节点运行，即将计算节点和存储节点放在一起运行，从而减少了节点间的数据移动开销。

MapReduce 的工作流程

工作流程概述

MapReduce的 核心思想可以用“分而治之”来描述，也就是把一个大的数据集拆分成多个小数据块在多台机器上并行处理，也就是说，一个大的 MapReduce 作业，首先会被拆分成许多个 Map 任务在多台机器上并行执行，每个 Map 任务通常运行在数据存储的节点上，这样，计算和数据就可以放在一起运行，不需要额外的数据传输开销。当 Map 任务结束后，会生成以 <key,value> 形式表示的许多中间结果。然后，这些中间结果会被分发到多个 Reduce 任务在多台机器上并行执行，具有相同 key 的 <key,value> 会被发送到同个 Reduce 任务那里，Reduce 任务会对中间结果进行汇总计算得到最后结果，并输出到分布式文件系统中。

需要指出的是，不同的 Map 任务之间不会进行通信，不同的 Reduce 任务之间也不会发生任何信息交换；用户不能显式地从一台机器向另台机器发送消息，所有的数据交换都是通过 MapReduce 框架自身去实现的。

在 MapReduce 的整个执行过程中，Map 任务的输人文件、Reduce 任务的处理结果都是保存在分布式文件系统中的，而 Map 任务处理得到的中间结果则保存在本地存储中（如磁盘）。另外，只有当 Map 处理全部结束后， Reduce 过程才能开始；只有 Map 需要考虑数据局部性，实现“计算向数据靠拢”，而 Reduce 则无需考虑数据局部性。

各个执行阶段

1. MapReduce 框架使用 InputFormat 模块做 Map 前的预处理，比如验证输人的格式是否符合输人定义；然后，将输人文件切分为逻辑上的多个 InputSplit，InputSplit 是 MapReduce 对文件进行处理和运算的输人单位，只是一个逻辑概念，每个 InputSplit 并没有对文件进行实际切割，只是记录了要处理的数据的位置和长度。
2. 因为 InputSplit 是逻辑切分而非物理切分，所以还需要通过 RecordReader（RR）根据 InputSplit 中的信息来处理 InputSplit 中的具体记录，加载数据并转换为适合 Map 任务读取的键值对，输人给 Map 任务。
3. Map 任务会根据用户自定义的映射规则，输出一系列的 <key,value> 作为中间结果。
4. 为了让 Reduce 可以并行处理 Map 的结果，需要对 Map 的输出进行一定的分区（Portition）、排序（Sort）、合并（Combine）、归并（Merge）等操作，得到 <key, value-list> 形式的中间结果，再交给对应的 Reduce 进行处理，这个过程称为 Shufle。从无序的 <key,value> 到有序的 <key, value-list>，这个过程用 Shuffle（洗牌）来称呼是非常形象的。
5. Reduce 以一系列 <key, value-list> 中间结果作为输人，执行用户定义的逻辑，输出结果给 OutputFormat 模块。
6. OutputFormat 模块会验证输出目录是否已经存在以及输出结果类型是否符合配置文件中的配置类型，如果都满足，就输出 Reduce 的结果到分布式文件系统。

Shuffle 过程详解

Shuffle 过程简介

所谓 Shuffle，是指对 Map 输出结果进行分区、排序、合并等处理并交给 Reduce 的过程。因此，Shuffle 过程分为 Map 端的操作和 Reduce 端的操作。

Map 端的 Shuffle 过程

Map 的输出结果首先被写入缓存，当缓存满时，就启动溢写操作，把缓存中的数据写入磁盘文件，并清空缓存。当启动溢写操作时，首先需要把缓存中的数据进行分区，然后对每个分区的数据进行排序（Sort）和合并（Combine），之后再写人磁盘文件。每次溢写操作会生成一个新的磁盘文件，随着 Map 任务的执行，磁盘中就会生成多个溢写文件。在 Map 任务全部结束之前，这些溢写文件会被归并（Merge）成一个大的磁盘文件，然后通知相应的 Reduce 任务来领取属于自己处理的数据。

输入数据和执行 Map 任务

Map 任务的输入数据一般保存在分布式文件系统（如 GFS 或 HDFS）的文件块中，这些文件块的格式是任意的，可以是文档，也可以是二进制格式的。Map 任务接受 <key, value>作为输入后，按一定的映射规则转换成一批 <key, value> 进行输出。

写入缓存

每个 Map 任务都会被分配一个缓存，Map 的输出结果不是立即写入磁盘，而是首先写人缓存。在缓存中积累一定数量的 Map 输出结果以后，再一次性批量写人磁盘，这样可以大大减少对磁盘 I/O 的影响。因为，磁盘包含机械部件，它是通过磁头移动和盘片的转动来寻址定位数据的，每次寻址的开销很大，如果每个 Map 输出结果都直接写人磁盘，会引入很多次寻址开销，而一次性批量写入，就只需要一次寻址、连续写入，大大降低了开销。需要注意的是，在写入缓存之前，key 与 value 值都会被序列化成字节数组。

溢写（分区、排序和合并）

提供给 MapReduce 的缓存的容量是有限的，默认大小是 100 MB。随着 Map 任务的执行，缓存中 Map 结果的数量会不断增加，很快就会占满整个缓存。这时，就必须启动溢写（Spill）操作，把缓存中的内容一次性写人磁盘，并清空缓存。溢写的过程通常是由另外个单独的后台线程来完成的，不会影响 Map 结果往缓存写人，但是为了保证 Map 结果能够不停地持续写入缓存，不受溢写过程的影响，就必须让缓存中一直有可用的空间，不能等到全部占满才启动溢写过程，所以一般会设置一个溢写比例，如0.8，也就是说，当 100 MB 大小的缓存被填满 80 MB 数据时，就启动溢写过程，把已经写人的 80 MB 数据写人磁盘，剩余 20 MB 空间供 Map 结果继续写人。

但是，在溢写到磁盘之前，缓存中的数据首先会被分区（Partition）。缓存中的数据是 <key, value> 形式的键值对，这些键值对最终需要交给不同的 Reduce 任务进行并行处理。MapReduce 通过 Partitioner 接口对这些键值对进行分区，默认采用的分区方式是采用 Hash 函数对 key 进行哈希后再用 Reduce 任务的数量进行取模，可以表示成 hash(key) mod R，其中 R 表示 Reduce 任务的数量，这样，就可以把 Map 输出结果均匀地分配给这 R 个Reduce 任务去并行处理了。当然，MapReduce 也允许用户通过重载 Partitioner 接口来自定义分区方式。

对于每个分区内的所有键值对，后台线程会根据 key 对它们进行内存排序（Sort），排序是 MapReduce 的默认操作。排序结束后，还包含一个可选的合并（Combine）操作。如果用户事先没有定义 Combiner 函数，就不用进行合并操作。如果用户事先定义了 Combiner 函数，则这个时候会执行合并操作，从而减少需要溢写到磁盘的数据量。

所谓“合并”，是指将那些具有相同 key 的 <key,value> 的 value 加起来。比如，有两个键值对 <“xmu" 1> 和 <“xmu” 1>，经过合并操作以后就可以得到一个键值对 <“xmu” 2>，减少了键值对的数量。这里需要注意，Map 端的这种合并操作，其实和 Reduce 的功能相似，但是由于这个操作发生在 Map 端，所以我们只能称之为“合并”，从而有别于 Reduce。不过，并非所有场合都可以使用 Combiner，因为 Combiner 的输出是 Reduce 任务的输人，Combiner 绝不能改变 Reduce 任务最终的计算结果，一般而言，累加、最大值等场景可以使用合并操作。

经过分区、排序以及可能发生的合并操作之后，这些缓存中的键值对就可以被写人磁盘，并清空缓存。每次溢写操作都会在磁盘中生成一个新的溢写文件，写人溢写文件中的所有键值对都是经过分区和排序的。

文件归并

每次溢写操作都会在磁盘中生成一个新的溢写文件，随着 MapReduce 任务的进行，磁盘中的溢写文件数量会越来越多。当然，如果 Map 输出结果很少，磁盘上只会存在一个溢写文件，但是通常都会存在多个溢写文件。最终，在 Map 任务全部结束之前，系统会对所有溢写文件中的数据进行归并（Merge），生成一个大的溢写文件，这个大的溢写文件中的所有键值对也是经过分区和排序的。

所谓“归并”，是指对于具有相同 key 的键值对会被归并成一个新的键值对。具体而言，对于若千个具有相同 key 的键值对 $<k_1,v_1>, <k_1,v_2> ….. <k_1,v_n>$ 会被归并成一个新的键值对 $<k_1, <v_1,v_2,…,v_n>$。

另外，进行文件归并时，如果磁盘中已经生成的溢写文件的数量超过参数 min.num.spills.for.combine 的值时（默认值是 3，用户可以修改这个值），那么，就可以再次运行 Combiner，对数据进行合并操作，从而减少写人磁盘的数据量。但是，如果磁盘中只有一两个溢写文件时，执行合并操作就会“得不偿失”，因为执行合并操作本身也需要代价，因此不会运行 Combiner。

经过上述4个步骤以后，Map 端的 Shuffle 过程全部完成，最终生成的一个大文件会被存放在本地磁盘上。这个大文件中的数据是被分区的，不同的分区会被发送到不同的 Reduce 任务进行并行处理。JobTracker 会一直监测 Map 任务的执行，当监测到一个 Map 任务完成后，就会立即通知相关的 Reduce 任务来“领取”数据，然后开始 Reduce 端的 Shuffle 过程。

Reduce 端的 Shuffle 过程

Reduce 任务从 Map 端的不同 Map 机器领回属于自己处理的那部分数据，然后对数据进行归并（Merge）后交给 Reduce 处理。

“领取”数据

Map 端的 Shuffle 过程结束后，所有 Map 输出结果都保存在 Map 机器的本地磁盘上，Reduce 任务需要把这些数据“领取”（Fetch）回来存放到自己所在机器的本地磁盘上。因此，在每个 Reduce 任务真正开始之前，它大部分时间都在从 Map 端把属于自己处理的那些分区的数据“领取”过来。每个 Reduce 任务会不断地通过 RPC 向 JobTracker 询问 Map 任务是否已经完成；JobTracker 监测到一个 Map 任务完成后，就会通知相关的 Reduce 任务来“领取”数据；一旦一个 Reduce 任务收到 JobTracker 的通知，它就会到该 Map 任务所在机器上把属于自已处理的分区数据领取到本地磁盘中。一般系统中会存在多个 Map 机器，因此 Reduce 任务会使用多个线程同时从多个 Map 机器领回数据。

归并数据

从Map端领回的数据会首先被存放在 Reduce 任务所在机器的缓存中，如果缓存被占满，就会像 Map 端一样被溢写到磁盘中。由于在 Shuffle 阶段 Reduce 任务还没有真正开始执行，因此，这时可以把内存的大部分空间分配给 Shuffle 过程作为缓存。需要注意的是，系统中一般存在多个 Map 机器，Reduce 任务会从多个 Map 机器领回属于自己处理的那些分区的数据，因此缓存中的数据是来自不同的 Map 机器的，一般会存在很多可以合并（Combine）的键值对。当溢写过程启动时，具有相同 key 的键值对会被归并（Merge），如果用户定义了 Combiner，则归并后的数据还可以执行合并操作，减少写人磁盘的数据量。每个溢写过程结束后，都会在磁盘中生成一个溢写文件，因此磁盘上会存在多个溢写文件。最终，当所有的 Map 端数据都已经被领回时，和 Map 端类似，多个溢写文件会被归并成开个大文件，归并的时候还会对键值对进行排序，从而使得最终大文件中的键值对都是有序的。当然，在数据很少的情形下，缓存可以存储所有数据，就不需要把数据溢写到磁盘，而是直接在内存中执行归并操作，然后直接输出给 Reduce 任务。

需要说明的是，把磁盘上的多个溢写文件归并成一个大文件可能需要执行多轮归并操作。每轮归并操作可以归并的文件数量是由参数 io.sort.factor 的值来控制的（默认值是 10，可以修改）。假设磁盘中生成了 50 个溢写文件，每轮可以归并 10 个溢写文件，则需要经过 5 轮归并，得到 5 个归并后的大文件。

把数据输人给 Reduce 任务

磁盘中经过多轮归并后得到的若干个大文件，不会继续归并成一个新的大文件，而是直接输入给 Reduce 任务，这样可以减少磁盘读写开销。由此，整个 Shuffle 过程顺利结束。接下来，Reduce 任务会执行 Reduce 函数中定义的各种映射，输出最终结果，并保存到分布式文件系统中（比如 GFS 或 HDFS）。

• 最简单的数据扩充方法就是垂直镜像对称，假如，训练集中有这张图片，然后将其翻转得到右边的图像。对大多数计算机视觉任务，左边的图片是猫，然后镜像对称仍然是猫，如果镜像操作保留了图像中想识别的物体的前提下，这是个很实用的数据扩充技巧。
• 另一个经常使用的技巧是随机裁剪，给定一个数据集，然后开始随机裁剪，可能修剪这个（编号1），选择裁剪这个（编号2），这个（编号3），可以得到不同的图片放在数据集中，你的训练集中有不同的裁剪。随机裁剪并不是一个完美的数据扩充的方法，如果你随机裁剪的那一部分（红色方框标记部分，编号4），这部分看起来不像猫。但在实践中，这个方法还是很实用的，随机裁剪构成了很大一部分的真实图片。
• 镜像对称和随机裁剪是经常被使用的。当然，理论上，你也可以使用旋转，剪切（shearing：此处并非裁剪的含义，图像仅水平或垂直坐标发生变化）图像，可以对图像进行这样的扭曲变形，引入很多形式的局部弯曲等等。当然使用这些方法并没有坏处，尽管在实践中，因为太复杂了所以使用的很少。

• 第二种经常使用的方法是彩色转换，有这样一张图片，然后给R、G和B三个通道上加上不同的失真值。

卷积网络与全连接网络比较

和只用全连接层相比，卷积层的两个主要优势在于参数共享和稀疏连接。

• 参数共享。观察发现，特征检测如垂直边缘检测如果适用于图片的某个区域，那么它也可能适用于图片的其他区域。也就是说，如果你用一个3×3的过滤器检测垂直边缘，那么图片的左上角区域，以及旁边的各个区域（左边矩阵中蓝色方框标记的部分）都可以使用这个3×3的过滤器。每个特征检测器以及输出都可以在输入图片的不同区域中使用同样的参数，以便提取垂直边缘或其它特征。它不仅适用于边缘特征这样的低阶特征，同样适用于高阶特征，例如提取脸上的眼睛，猫或者其他特征对象。即使减少参数个数，这9个参数同样能计算出16个输出。直观感觉是，一个特征检测器，如垂直边缘检测器用于检测图片左上角区域的特征，这个特征很可能也适用于图片的右下角区域。因此在计算图片左上角和右下角区域时，你不需要添加其它特征检测器。假如有一个这样的数据集，其左上角和右下角可能有不同分布，也有可能稍有不同，但很相似，整张图片共享特征检测器，提取效果也很好。
• 使用稀疏连接。0是通过3×3的卷积计算得到的，它只依赖于这个3×3的输入的单元格，右边这个输出单元（元素0）仅与36个输入特征中9个相连接。而且其它像素值都不会对输出产生任影响，这就是稀疏连接的概念。

神经网络可以通过这两种机制减少参数，以便我们用更小的训练集来训练它，从而预防过度拟合。

经典网络

LeNet-5

AlexNet

VGG16

残差网络（ResNets）（Residual Networks）

非常非常深的神经网络是很难训练的，因为存在梯度消失和梯度爆炸问题。跳跃连接（Skip connection），它可以从某一层网络层获取激活，然后迅速反馈给另外一层，甚至是神经网络的更深层。我们可以利用跳跃连接构建能够训练深度网络的 ResNets。

谷歌 Inception 网络

瓶颈层也是网络中最小的部分，我们先缩小网络表示，然后再扩大它。

说明：__池化层__。为了能在最后将这些输出都连接起来，我们会使用same类型的padding来池化，使得输出的高和宽依然是28×28，这样才能将它与其他输出连接起来。但注意，如果你进行了最大池化，即便用了same padding，3×3的过滤器，stride为1，其输出将会是28×28×192，其通道数或者说深度与这里的输入（通道数）相同。所以看起来它会有很多通道，我们实际要做的就是再加上一个1×1的卷积层，去进行我们在1×1卷积层的视频里所介绍的操作，将通道的数量缩小，缩小到28×28×32。也就是使用32个维度为1×1×192的过滤器，所以输出的维度其通道数缩小为32。这样就避免了最后输出时，池化层占据所有的通道。

在网络的最后几层，通常称为全连接层，在它之后是一个softmax层（编号1）来做出预测，这些分支（编号2）所做的就是通过隐藏层（编号3）来做出预测，所以这其实是一个softmax输出（编号2），这（编号1）也是。这是另一条分支（编号4），它也包含了一个隐藏层，通过一些全连接层，然后有一个softmax来预测，输出结果的标签。

你应该把它看做Inception网络的一个细节，它确保了即便是隐藏单元和中间层（编号5）也参与了特征计算，它们也能预测图片的分类。它在Inception网络中，起到一种调整的效果，并且能防止网络发生过拟合。

有两套方案：

• jedi

  1 2 3

  { "python.jediEnabled": true, }

• Microsoft.python.language server + intellicode

小括号补全

1
2
3

{
    "python.autoComplete.addBrackets": true
}

逻辑回归

以下以逻辑回归为例（向量都默认为列向量）：

$$
z^{(1)} = w^T x^{(1)} + b \
a^{(1)} = \sigma (z^{(1)}) \
z^{(2)} = w^T x^{(2)} + b \
a^{(2)} = \sigma (z^{(2)}) \
z^{(3)} = w^T x^{(3)} + b \
a^{(3)} = \sigma (z^{(3)}) \
$$

以上是一般形式。

__多样本向量化__。对于一个矩阵 $X = [x^{(1)} x^{(2)} \cdots x^{(m)}]$（每一个输入 $x$ 有 $n_x$ 个参数，即大小为 $(n_x, 1)$）作为训练输入时，可有以下表示：
$
Z = [z^{(1)} z^{(2)} \cdots z^{(m)}] = w^T X + [b b \cdots b] \
A = [a^{(1)} a^{(2)} \cdots a^{(m)}] = \sigma(Z)
$

神经网络

以单层神经网络为例：
$$
z^{[1]}_1 = w^{[1]T}_1x + b^{[1]}_1, a^{[1]}_1 = \sigma(z^{[1]}_1) \
z^{[1]}_2 = w^{[1]T}_2x + b^{[1]}_2, a^{[1]}_2 = \sigma(z^{[1]}_2) \
z^{[1]}_3 = w^{[1]T}_3x + b^{[1]}_3, a^{[1]}_3 = \sigma(z^{[1]}_3) \
z^{[1]}_4 = w^{[1]T}_4x + b^{[1]}_4, a^{[1]}_4 = \sigma(z^{[1]}_4) \
$$

向量化：
$$
a^{[1]} =
\left[
\begin{array}{c}
a^{[1]}{1}\
a^{[1]}{2}\
a^{[1]}{3}\
a^{[1]}{4}
\end{array}
\right]
= \sigma(z^{[1]}) \

\left[
\begin{array}{c}
z^{[1]}{1}\
z^{[1]}{2}\
z^{[1]}{3}\
z^{[1]}{4}\
\end{array}
\right]
=
\overbrace{
\left[
\begin{array}{c}
…w^{[1]T}{1}…\
…w^{[1]T}{2}…\
…w^{[1]T}{3}…\
…w^{[1]T}{4}…
\end{array}
\right]
}^{W^{[1]}}
*
\overbrace{
\left[
\begin{array}{c}
x_1\
x_2\
x_3\
\end{array}
\right]
}^{input}
+
\overbrace{
\left[
\begin{array}{c}
b^{[1]}_1\
b^{[1]}_2\
b^{[1]}_3\
b^{[1]}_4\
\end{array}
\right]
}^{b^{[1]}}
$$

多样本向量化：
$$
x =
\left[
\begin{array}{c}
\vdots & \vdots & \vdots & \vdots\
x^{(1)} & x^{(2)} & \cdots & x^{(m)}\
\vdots & \vdots & \vdots & \vdots\
\end{array}
\right] \

Z^{[1]} =
\left[
\begin{array}{c}
\vdots & \vdots & \vdots & \vdots\
z^{1} & z^{1} & \cdots & z^{1}\
\vdots & \vdots & \vdots & \vdots\
\end{array}
\right] \

A^{[1]} =
\left[
\begin{array}{c}
\vdots & \vdots & \vdots & \vdots\
\alpha^{1} & \alpha^{1} & \cdots & \alpha^{1}\
\vdots & \vdots & \vdots & \vdots\
\end{array}
\right] \

\left.
\begin{array}{r}
\text{$z^{1} = W^{1}x^{(i)} + b^{[1]}$}\
\text{$\alpha^{1} = \sigma(z^{1})$}\
\text{$z^{2} = W^{2}\alpha^{1} + b^{[2]}$}\
\text{$\alpha^{2} = \sigma(z^{2})$}\
\end{array}
\right}
\implies
\begin{cases}
\text{$A^{[1]} = \sigma(z^{[1]})$}\
\text{$z^{[2]} = W^{[2]}A^{[1]} + b^{[2]}$}\
\text{$A^{[2]} = \sigma(z^{[2]})$}\
\end{cases}
$$

说明

• $a^{m}$：表示第个 n 训练样本的第 m 层。
• $W^{[m]}_n$：表示第 m 层的第 n 个节点。

转自：https://zhuanlan.zhihu.com/p/113917726

一

MySQL 作为互联网中非常热门的数据库，其底层的存储引擎和数据检索引擎的设计非常重要，尤其是 MySQL 数据的存储形式以及索引的设计，决定了 MySQL 整体的数据检索性能。

我们知道，索引的作用是做数据的快速检索，而快速检索的实现的本质是数据结构。通过不同数据结构的选择，实现各种数据快速检索。在数据库中，高效的查找算法是非常重要的，因为数据库中存储了大量数据，一个高效的索引能节省巨大的时间。比如下面这个数据表，如果 MySQL 没有实现索引算法，那么查找 id=7 这个数据，那么只能采取暴力顺序遍历查找，找到 id=7 这个数据需要比较 7 次，如果这个表存储的是 1000W 个数据，查找 id=1000W 这个数据那就要比较 1000W 次，这种速度是不能接受的。

Mysql 索引底层数据结构选型

哈希表（Hash）

哈希表是做数据快速检索的有效利器。

哈希算法：也叫散列算法，就是把任意值（key）通过哈希函数变换为固定长度的 key 地址，通过这个地址进行具体数据的数据结构。

考虑这个数据库表 user，表中一共有 7 个数据，我们需要检索 id=7 的数据，SQL 语法是：

1

select \* from user where id=7;

哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存储的额数据的物理地址，通过该独立地址可以找到对应 user_name=’g’这个数据。这就是哈希算法快速检索数据的计算过程。

但是哈希算法有个数据碰撞的问题，也就是哈希函数可能对不同的 key 会计算出同一个结果，比如 hash(7)可能跟 hash(199)计算出来的结果一样，也就是不同的 key 映射到同一个结果了，这就是碰撞问题。解决碰撞问题的一个常见处理方式就是链地址法，即用链表把碰撞的数据接连起来。计算哈希值之后，还需要检查该哈希值是否存在碰撞数据链表，有则一直遍历到链表尾，直达找到真正的 key 对应的数据为止。

从算法时间复杂度分析来看，哈希算法时间复杂度为 O（1），检索速度非常快。比如查找 id=7 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法，这是为什么呢？

因为考虑到数据检索有一个常用手段就是范围查找，比如以下这个 SQL 语句：

1

select \* from user where id \>3;

针对以上这个语句，我们希望做的是找出 id>3 的数据，这是很典型的范围查找。如果使用哈希算法实现的索引，范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了，没有一点效率而言。

所以，使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。

二叉查找树(BST)

二叉查找树是一种支持数据快速查找的数据结构，如图下所示:

二叉查找树的时间复杂度是 $O(lgn)$，比如针对上面这个二叉树结构，我们需要计算比较 3 次就可以检索到 id=7 的数据，相对于直接遍历查询省了一半的时间，从检索效率上看来是能做到高速检索的。此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢？

答案是可以的。观察上面的图，二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找 id>5 的数据，那我们取出节点为 6 的节点以及其右子树就可以了，范围查找也算是比较容易实现。

但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 $O(N)$，检索性能急剧下降。比如以下这个情况，二叉树已经极度不平衡了，已经退化为链表了，检索速度大大降低。此时检索 id=7 的数据的所需要计算的次数已经变为 7 了。

在数据库中，数据的自增是一个很常见的形式，比如一个表的主键是 id，而主键一般默认都是自增的，如果采取二叉树这种数据结构作为索引，那上面介绍到的不平衡状态导致的线性查找的问题必然出现。因此，简单的二叉查找树存在不平衡导致的检索性能降低的问题，是不能直接用于实现 MySQL 底层索引的。

AVL 树和红黑树

二叉查找树存在不平衡问题，因此学者提出通过树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态，就能保持二叉查找树的最佳查找性能了。基于这种思路的自调整平衡状态的二叉树有 AVL 树和红黑树。

首先简单介绍红黑树，这是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态（时间复杂度为 $O(logn)$），也就保证了查找效率不会明显减低。比如从 1 到 7 升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态，如下图所示。下面这个红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率。

红黑树拥有不错的平均查找效率，也不存在极端的 $O(n)$ 情况，那红黑树作为 MySQL 底层索引实现是否可以呢？其实红黑树也存在一些问题，观察下面这个例子。

红黑树顺序插入 1~7 个节点，查找 id=7 时需要计算的节点数为 4。

红黑树顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 6 次。观察一下这个树的形态，是不是当数据是顺序插入时，树的形态一直处于“右倾”的趋势呢？从根本上上看，红黑树并没有完全解决二叉查找树虽然这个“右倾”趋势远没有二叉查找树退化为线性链表那么夸张，但是数据库中的基本主键自增操作，主键一般都是数百万数千万的，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗，我们数据库不可能忍受这种无意义的等待的。

现在考虑另一种更为严格的自平衡二叉树 AVL 树。因为 AVL 树是个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能会更多。

AVL 树顺序插入 1~7 个节点，查找 id=7 所要比较节点的次数为 3。

AVL 树顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 4。从查找效率而言，AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。从树的形态看来，AVL 树不存在红黑树的“右倾”问题。也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。

总结一下 AVL 树的优点：

1. 不错的查找性能（$O(logn)$），不存在极端的低效查找的情况。
2. 可以实现范围查找、数据排序。

看起来 AVL 树作为数据查找的数据结构确实很不错，但是 AVL 树并不适合做 MySQL 数据库的索引数据结构，因为考虑一下这个问题：

数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

B 树

下面这个 B 树，每个节点限制最多存储两个 key，一个节点如果超过两个 key 就会自动分裂。比如下面这个存储了 7 个数据 B 树，只需要查询两个节点就可以知道 id=7 这数据的具体位置，也就是两次磁盘 IO 就可以查询到指定数据，优于 AVL 树。

下面是一个存储了 16 个数据的 B 树，同样每个节点最多存储 2 个 key，查询 id=16 这个数据需要查询比较 4 个节点，也就是经过 4 次磁盘 IO。看起来查询性能与 AVL 树一样。

但是考虑到磁盘 IO 读一个数据和读 100 个数据消耗的时间基本一致，那我们的优化思路就可以改为：尽可能在一次磁盘 IO 中多读一点数据到内存。这个直接反映到树的结构就是，每个节点能存储的 key 可以适当增加。

当我们把单个节点限制的 key 个数设置为 6 之后，一个存储了 7 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。

一个存储了 16 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。相对于 AVL 树而言磁盘 IO 次数降低为一半。

所以数据库索引数据结构的选型而言，B 树是一个很不错的选择。总结来说，B 树用作数据库索引有以下优点：

1. 优秀检索速度，时间复杂度：B 树的查找性能等于 $O(h*logn)$，其中 h 为树高，n 为每个节点关键词的个数；
2. 尽可能少的磁盘 IO，加快了检索速度；
3. 可以支持范围查找。

B+树

B 树和 B+树有什么不同呢？

第一，B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。

第二，B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

通过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

Innodb 引擎和 Myisam 引擎的实现

Mysql 底层数据引擎以插件形式设计，最常见的是 Innodb 引擎和 Myisam 引擎，用户可以根据个人需求选择不同的引擎作为 Mysql 数据表的底层引擎。我们刚分析了，B+树作为 Mysql 的索引的数据结构非常合适，但是数据和索引到底怎么组织起来也是需要一番设计，设计理念的不同也导致了 Innodb 和 Myisam 的出现，各自呈现独特的性能。

MyISAM 虽然数据查找性能极佳，但是不支持事务处理。Innodb 最大的特色就是支持了 ACID 兼容的事务功能，而且他支持行级锁。Mysql 建立表的时候就可以指定引擎，比如下面的例子，就是分别指定了 Myisam 和 Innodb 作为 user 表和 user2 表的数据引擎。

执行这两个指令后，系统出现了以下的文件，说明这两个引擎数据和索引的组织方式是不一样的。

Innodb 创建表后生成的文件有：

• frm:创建表的语句
• idb:表里面的数据+索引文件

Myisam 创建表后生成的文件有

• frm:创建表的语句
• MYD:表里面的数据文件（myisam data）
• MYI:表里面的索引文件（myisam index）

从生成的文件看来，这两个引擎底层数据和索引的组织方式并不一样，MyISAM 引擎把数据和索引分开了，一人一个文件，这叫做非聚集索引方式；Innodb 引擎把数据和索引放在同一个文件里了，这叫做聚集索引方式。下面将从底层实现角度分析这两个引擎是怎么依靠 B+树这个数据结构来组织引擎实现的。

MyISAM 引擎的底层实现（非聚集索引方式）

MyISAM 用的是非聚集索引方式，即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

当我们为某个字段添加索引时，我们同样会生成对应字段的索引树，该字段的索引树的叶子节点同样是记录了对应数据的物理地址，然后也是拿着这个物理地址去数据文件里定位到具体的数据记录。

Innodb 引擎的底层实现（聚集索引方式）

InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，如左下图所示，而 B+树的叶子节点存储的是主键 ID 对应的数据，比如在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name=’Bob’。

这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。注意，叶子存储的是主键 KEY！拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

问题来了，为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存具体数据呢，而要多此一举先找到主键，再在主键索引树找到对应的数据呢?

其实很简单，因为 InnoDB 需要节省存储空间。一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大（数据极度冗余了）。从节约磁盘空间的角度来说，真的没有必要每个字段索引树都存具体数据，通过这种看似“多此一举”的步骤，在牺牲较少查询的性能下节省了巨大的磁盘空间，这是非常有值得的。

在进行 InnoDB 和 MyISAM 特点对比时谈到，MyISAM 查询性能更好，从上面索引文件数据文件的设计来看也可以看出原因：MyISAM 直接找到物理地址后就可以直接定位到数据记录，但是 InnoDB 查询到叶子节点后，还需要再查询一次主键索引树，才可以定位到具体数据。等于 MyISAM 一步就查到了数据，但是 InnoDB 要两步，那当然 MyISAM 查询性能更高。

本文首先探讨了哪种数据结构更适合作为 Mysql 底层索引的实现，然后再介绍了 Mysql 两种经典数据引擎 MyISAM 和 InnoDB 的底层实现。最后再总结一下什么时候需要给你的表里的字段加索引吧：

1. 较频繁的作为查询条件的字段应该创建索引；
2. 唯一性太差的字段不适合单独创建索引，即使该字段频繁作为查询条件；
3. 更新非常频繁的字段不适合创建索引。

转自：https://zhuanlan.zhihu.com/p/81273236

二

InnoDB的一棵B+树可以存放多少行数据？

答案：约2千万

为什么是这么多？
因为这是可以算出来的，要搞清楚这个问题，先从InnoDB索引数据结构、数据组织方式说起。

计算机在存储数据的时候，有最小存储单元，这就好比现金的流通最小单位是一毛。

在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）的最小单元是块，一个块的大小是4k，而对于InnoDB存储引擎也有自己的最小储存单元，页（Page），一个页的大小是16K。

下面几张图可以理解最小存储单元：

文件系统中一个文件大小只有1个字节，但不得不占磁盘上4KB的空间。

InnoDB的所有数据文件（后缀为ibd的文件），大小始终都是16384（16k）的整数倍。

磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

在MySQL中，InnoDB页的大小默认是16k，当然也可以通过参数设置：

表中的数据都是存储在页中的，所以一个页中能存储多少行数据呢？

假设一行数据的大小是1k，那么一个页可以存放16行这样的数据。

如果数据库只按这样的方式存储，如何查找数据就成为一个问题，因为不知道要查找的数据存在哪个页中，也不可能把所有的页遍历一遍，那样太慢了。

不过，可以使用B+树的方式组织这些数据，如图所示：

先将数据记录按主键进行排序，分别存放在不同的页中（为了便于理解这里一个页中只存放3条记录，实际情况可以存放很多）

除了存放数据的页以外，还有存放键值+指针的页，如图中page number=3的页，该页存放键值和指向数据页的指针，这样的页由N个键值+指针组成。

当然它也是排好序的。这样的数据组织形式，我们称为索引组织表。

现在来看下，要查找一条数据，怎么查？

如：select * from user where id=5;

这里id是主键，通过这棵B+树来查找，首先找到根页，你怎么知道user表的根页在哪呢？

其实每张表的根页位置在表空间文件中是固定的，即page number=3的页。

找到根页后通过二分查找法，定位到id=5的数据应该在指针P5指向的页中，那么进一步去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录：

1

| 5 | zhao2 | 27 |

现在清楚了InnoDB中主键索引B+树是如何组织数据、查询数据的。

总结一下：

• InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。
• 索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据；
  那么回到我们开始的问题，通常一棵B+树可以存放多少行数据？

这里我们先假设B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数*单个叶子节点记录行数。

上文已经说明单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在需要计算出非叶子节点能存放多少指针？

其实这也很好算，假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节

我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。

那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样的原理可以算出一个高度为3的B+树可以存放：1170117016=21902400 条这样的记录。

所以在 InnoDB 中 B+ 树高度一般为1-3层，它就能满足千万级的数据存储。

在查找数据时，一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

怎么得到InnoDB主键索引 B+ 树的高度？

上面通过推断得出 B+ 树的高度通常是 1-3，下面从另外一个侧面证明这个结论。

在 InnoDB 的表空间文件中，约定page number为 3的代表主键索引的根页，而在根页偏移量为 64的地方存放了该 B+ 树的 page level。

如果 page level 为 1，树高为 2，page level 为 2，则树高为 3。即 B+树的高度=page level+1；下面将从实际环境中尝试找到这个 page level。

在实际操作之前，可以通过InnoDB元数据表确认主键索引根页的page number为3，也可以从《InnoDB存储引擎》这本书中得到确认。

可以看出数据库dbt3下的customer表、lineitem表主键索引根页的page number均为3，而其他的二级索引page number为4。

关于二级索引与主键索引的区别请参考MySQL相关书籍，本文不在此介绍。

下面对数据库表空间文件做想相关的解析：

因为主键索引B+树的根页在整个表空间文件中的第3个页开始，所以可以算出它在文件中的偏移量：16384*3=49152（16384为页大小）。

另外根据《InnoDB存储引擎》中描述在根页的64偏移量位置前2个字节，保存了page level的值

因此我想要的page level的值在整个文件中的偏移量为：16384*3+64=49152+64=49216，前2个字节中。

接下来用hexdump工具，查看表空间文件指定偏移量上的数据：

linetem表的page level为2，B+树高度为page level+1=3；

region表的page level为0，B+树高度为page level+1=1；

customer表的page level为2，B+树高度为page level+1=3；

这三张表的数据量如下：

总结：

lineitem表的数据行数为600多万，B+树高度为3，customer表数据行数只有15万，B+树高度也为3。可以看出尽管数据量差异较大，这两个表树的高度都是3

换句话说这两个表通过索引查询效率并没有太大差异，因为都只需要做3次IO。那么如果有一张表行数是一千万，那么他的B+树高度依旧是3，查询效率仍然不会相差太大。

region表只有5行数据，当然他的B+树高度为1。

面试题

有一道MySQL的面试题，为什么MySQL的索引要使用B+树而不是其它树形结构?比如B树？

这个问题的复杂版本可以参考本文；

简单回答是：

因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少（有些资料也称为扇出）

指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低；

小结

本文从一个问题出发，逐步介绍了InnoDB索引组织表的原理、查询方式，并结合已有知识，回答该问题，结合实践来证明。

当然为了表述简单易懂，文中忽略了一些细枝末节，比如一个页中不可能所有空间都用于存放数据，它还会存放一些少量的其他字段比如page level，index number等等，另外还有页的填充因子也导致一个页不可能全部用于保存数据。

转自：https://www.cnblogs.com/rjzheng/p/9915754.html

三

引言

回想四年前，我在学习mysql的索引这块的时候，老师在讲索引的时候，是像下面这么说的

索引就像一本书的目录。而当用户通过索引查找数据时，就好比用户通过目录查询某章节的某个知识点。这样就帮助用户有效地提高了查找速度。所以，使用索引可以有效地提高数据库系统的整体性能。

嗯，这么说其实也对。但是呢，大家看完这种说法，其实可能还是觉得太抽象了！因此呢，我还想再深入的细说一下，所以就有了此文！

需要说明的是，我说的内容只在Mysql的Innodb引擎中是成立的。在Sql Server、oracle、Mysql的Mysiam引擎中的正确性，不一定成立！

OK，废话不多说，开始啰嗦!

正文

索引的科普

先引进聚簇索引和非聚簇索引的概念！

我们平时在使用的Mysql中，使用下述语句

1
2
3
4
5
6

CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
    [USING index_type]
    ON tbl_name (index_col_name,...)
 
index_col_name:
    col_name [(length)] [ASC | DESC]

创建的索引，如复合索引、前缀索引、唯一索引，都是属于非聚簇索引，在有的书籍中，又将其称为辅助索引(secondary index)。在后文中，我们称其为非聚簇索引，其数据结构为B+树。

那么，这个聚簇索引，在Mysql中是没有语句来另外生成的。在Innodb中，Mysql中的数据是按照主键的顺序来存放的。那么聚簇索引就是按照每张表的主键来构造一颗B+树，叶子节点存放的就是整张表的行数据。由于表里的数据只能按照一颗B+树排序，因此一张表只能有一个聚簇索引。

在Innodb中，聚簇索引默认就是主键索引。

这个时候，机智的读者，应该要问我

如果我的表没建主键呢？

回答是，如果没有主键，则按照下列规则来建聚簇索引

• 没有主键时，会用一个唯一且不为空的索引列做为主键，成为此表的聚簇索引
• 如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

ps:大家还记得，自增主键和uuid作为主键的区别么？由于主键使用了聚簇索引，如果主键是自增id，，那么对应的数据一定也是相邻地存放在磁盘上的，写入性能比较高。如果是uuid的形式，频繁的插入会使innodb频繁地移动磁盘块，写入性能就比较低了。

索引原理介绍

先来一张带主键的表，如下所示，pId是主键

画出该表的结构图如下

如上图所示，分为上下两个部分，上半部分是由主键形成的B+树，下半部分就是磁盘上真实的数据！那么，当我们， 执行下面的语句

1

select * from table where pId='11'

那么，执行过程如下

如上图所示，从根开始，经过3次查找，就可以找到真实数据。如果不使用索引，那就要在磁盘上，进行逐行扫描，直到找到数据位置。显然，使用索引速度会快。但是在写入数据的时候，需要维护这颗B+树的结构，因此写入性能会下降！

OK，接下来引入非聚簇索引!我们执行下面的语句

1

create index index_name on table(name);

此时结构图如下所示

大家注意看，会根据你的索引字段生成一颗新的B+树。因此， 我们每加一个索引，就会增加表的体积， 占用磁盘存储空间。然而，注意看叶子节点，非聚簇索引的叶子节点并不是真实数据，它的叶子节点依然是索引节点，存放的是该索引字段的值以及对应的主键索引(聚簇索引)。

如果我们执行下列语句

1

select * from table where name='lisi'

此时结构图如下所示

通过上图红线可以看出，先从非聚簇索引树开始查找，然后找到聚簇索引后。根据聚簇索引，在聚簇索引的B+树上，找到完整的数据！

什么情况不去聚簇索引树上查询呢？

还记得我们的非聚簇索引树上存着该索引字段的值么。如果，此时我们执行下面的语句

1

select name from table where name='lisi'

此时结构图如下

如上图红线所示，如果在非聚簇索引树上找到了想要的值，就不会去聚簇索引树上查询。还记得，博主在《select的正确姿势》提到的索引问题么：

当执行select col from table where col = ?，col上有索引的时候，效率比执行select * from table where col = ? 速度快好几倍！

看完上面的图，你应该对这句话有更深层的理解了。

那么这个时候，我们执行了下述语句，又会发生什么呢？

1

create index index_birthday on table(birthday);

此时结构图如下

看到了么，多加一个索引，就会多生成一颗非聚簇索引树。因此，很多文章才说，索引不能乱加。因为，有几个索引，就有几颗非聚簇索引树！你在做插入操作的时候，需要同时维护这几颗树的变化！因此，如果索引太多，插入性能就会下降!

总结

讲到这里，大家应该清楚的明白索引的原理了！可能细节方面还不够严谨，但是我觉得一个研发，理解到这里可以了，够用了，毕竟我们也不是专业的DBA。
希望大家有所收获！

Oracle Java 8/9/10不再可用于公共下载（许可证更改）。

要从 AdoptOpenJDK 安装 JDK：

1. brew tap adoptopenjdk/openjdk
2. brew search java

• 语料库（corpus）：就是存放语言材料的仓库（语言数据库）。
• 语料库语言学（corpus linguistics）：基于语料库进行语言学研究

按内容构成和目的划分：

• 异质的（heterogeneous）[黄昌宁，2002]：最简单的语料收集方法，没有事先规定和选材原则。
• 同质的（homogeneous）：与“异质”正好相反，比如美国的 TIPSTER 项目只收集军事方面的文本。
• 系统的（systematic）：充分考虑语料的动态和静态问题、代表性和平衡问题以及语料库的规模等问题。
• 专用的（specialized）：如：北美的人文科学语料库。

按语言种类划分：

• 单语的
• 双语的或多语的
  • 篇章对齐
  • 句子对齐
  • 结构对齐

是否标注

• 具有词性标注
• 句法结构信息标注（树库）
• 语义信息标注

平衡语料库

• 平衡语料库着重考虑语料的代表性与平衡性。
• 语料采集的七项原则：语料的真实性、可靠性、科学性、代表性、权威性、分布性和流通性。其中，语料的分布性还要考虑语料的科学领域分布、地域分布、时间分布和语体分布等。-[张普, 2003]

平行语料库，两种含义：

• 一种是指在同一种语言的语料上的平行，例如，“国际英语语料库”，共有 20 个平行的子语料库，分别来自以英语为母语或官方语言和主要语言的国家，如英国、美国、加拿大、澳大利亚、新西兰等。其平行性表现为语料选取的时间、对象、比例、文本数、文本长度等几乎是一致的。建库的目的是对不同国家的英语进行对比研究。
• 另一种平行语料库是指在两种或多种语言之间的平行采样和加工。

• 共时语料库：是为了对语言进行共时（同一时段）研究而建立的语料库。研究大树的横断面所见的细胞和细胞关系，即研究一个共时平面中的元素与元素的关系。
• 历时语料库：是为了对语言进行历时研究而建立的语料库。研究大树的纵剖面所见的每个细胞和细胞关系的演变，即研究一个历时切面中元素与元素关系的演化。

判断历时语料库的 4 条原则 [张普, 2003]：

1. 是否动态：语料库必须是开放的、动态的。
2. 文本是否具有量化的流通度属性：所有的语料都应来源于大众传媒，具有与传媒特色相应的流通度属性。其量化的属性值也是动态的。
3. 深加工是否基于动态的加工方法：随语料的动态变化采集，并进行动态地加工。
4. 是否取得动态的加工结果：语料的加工结果也是动态的和历时的。