❶ 数据库索引为什么使用B+树
B tree： 二叉树（Binary tree），每个节点只能存储一个数。
B-tree： B树（B-Tree，并不是B“减”树，横杠为连接符，容易被误导）
B树属于多叉树又名平衡多路查找树。每个节点可以多个数（由磁盘大小决定）。
B+tree 和 B*tree 都是 B-tree的变种
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。而B-/+/*Tree，经过改进可以有效的利用系统对磁盘的块读取特性，在读取相同磁盘块的同时，尽可能多的加载索引数据，来提高索引命中效率，从而达到减少磁盘IO的读取次数。
不了解磁盘相关知识的可以查看 硬盘基本知识（磁头、磁道、扇区、柱面）
下面通过示意图来看一下，B-tree、B+tree、B*tree
从图中可以看出，B-tree 利用了磁盘块的特性进行构建的树。每个磁盘块一个节点，每个节点包含了很关键字。把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。
B-tree巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（每页为4K），这样每个节点只需要一次I/O就可以完全载入。
B-tree 的数据可以存在任何节点中。
B+tree 是 B-tree 的变种，数据只能存储在叶子节点。
B+tree 是 B-tree 的变种，B+tree 数据只存储在叶子节点中。这样在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定;
B*tree 每个磁盘块中又添加了对下一个磁盘块的引用。这样可以在当前磁盘块满时，不用扩容直接存储到下一个临近磁盘块中。当两个邻近的磁盘块都满时，这两个磁盘块各分出1/3的数据重新分配一个磁盘块，这样这三个磁盘块的数据都为2/3。
在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；
❷ sqlserver 存储二叉树
看看数据表结构
表：Tree
current_id int （当前节点编号）
father_id int （父节点编号，如果是根节点，-1）
left_id int （左节点编号）
right_id int （右节点编号）
表：Node
Node_id int PK
Node_vaule nvarchar(100)
说明：Tree表是用来存储树型结构的，Node表是用来存储节点内容的
其中Tree表的current_id与Node表的Node_id是一一对应的
至于遍历的存储过程是要完成什么功能呢？
❸ 试找出分别满足下面条件的所有二叉树
先序遍历：根->左子树->右子树
中序遍历：左子树->根->右子树
后序遍历：左子树->右子树->根
(1)先序遍历序列和中序遍历序列相同的话，则没有左子树，其遍历序列相同，如下形式
A
\
B
\
C
其先序中序遍历都是ABC
(2)中序遍历序列和后序遍历序列相同，则没有右子树，如下形式的
A
/
B
/
C
(3)先序遍历序列和后序遍历序列相同，只有根的结点没有左右子树的情况。
❹ sql数据库 建立三个表 student（学号 姓名 性别） sc（学号 课程号 成绩）course（课程号 课程名 分数 ）
select 姓名,savg from (select 学号，avg（成绩）as savg from sc where 成绩<60 group by 学号 having count(学号)>=2) t1,student where t1.学号=student.学号
1. Group By 语句简介：
Group By语句从英文的字面意义上理解就是“根据(by)一定的规则进行分组(Group)”。它的作用是通过一定的规则将一个数据集划分成若干个小的区域，然后针对若干个小区域进行数据处理。 2. Group By 的使用： 上面已经给出了对Group By语句的理解。基于这个理解和SQL Server 2000的联机帮助，下面对Group By语句的各种典型使用进行依次列举说明。 2.1 Group By [Expressions]: 这个恐怕是Group By语句最常见的用法了，Group By + [分组字段](可以有多个)。在执行了这个操作以后，数据集将根据分组字段的值将一个数据集划分成各个不同的小组。比如有如下数据集，其中水果名称(FruitName)和出产国家(ProctPlace)为联合主键： FruitName ProctPlace Price
Apple China $1.1
Apple Japan $2.1
Apple USA $2.5
Orange China $0.8
Banana China $3.1
Peach USA $3.0
如果我们想知道每个国家有多少种水果，那么我们可以通过如下SQL语句来完成： SELECT COUNT(*) AS 水果种类, ProctPlace AS 出产国 FROM T_TEST_FRUITINFO GROUP BY ProctPlace 这个SQL语句就是使用了Group By + 分组字段的方式，那么这句SQL语句就可以解释成“我按照出产国家(ProctPlace)将数据集进行分组，然后分别按照各个组来统计各自的记录数量。”很好理解对吧。这里值得注意的是结果集中有两个返回字段，一个是ProctPlace(出产国), 一个是水果种类。如果我们这里水果种类不是用Count(*)，而是类似如下写法的话： SELECT FruitName, ProctPlace FROM T_TEST_FRUITINFO GROUP BY ProctPlace 那么SQL在执行此语句的时候会报如下的类似错误： 选择列表中的列 'T_TEST_FRUITINFO.FruitName' 无效，因为该列没有包含在聚合函数或 GROUP BY 子句中。 这就是我们需要注意的一点，如果在返回集字段中，这些字段要么就要包含在Group By语句的后面，作为分组的依据；要么就要被包含在聚合函数中。我们可以将Group By操作想象成如下的一个过程，首先系统根据SELECT 语句得到一个结果集，如最开始的那个水果、出产国家、单价的一个详细表。然后根据分组字段，将具有相同分组字段的记录归并成了一条记录。这个时候剩下的那些不存在于Group By语句后面作为分组依据的字段就有可能出现多个值，但是目前一种分组情况只有一条记录，一个数据格是无法放入多个数值的，所以这里就需要通过一定的处理将这些多值的列转化成单值，然后将其放在对应的数据格中，那么完成这个步骤的就是聚合函数。这就是为什么这些函数叫聚合函数(aggregate functions)了。 2.2 Group By All [expressions] ： Group By All + 分组字段, 这个和前面提到的Group By [Expressions]的形式多了一个关键字ALL。这个关键字只有在使用了where语句的，且where条件筛选掉了一些组的情况才可以看出效果。在SQL Server 2000的联机帮助中，对于Group By All是这样进行描述的： 如果使用 ALL 关键字，那么查询结果将包括由 GROUP BY 子句产生的所有组，即使某些组没有符合搜索条件的行。没有 ALL 关键字，包含 GROUP BY 子句的 SELECT 语句将不显示没有符合条件的行的组。 其中有这么一句话“如果使用ALL关键字，那么查询结果将包含由Group By子句产生的所有组...没有ALL关键字，那么不显示不符合条件的行组。”这句话听起来好像挺耳熟的，对了，好像和LEFT JOIN 和 RIGHT JOIN 有点像。其实这里是类比LEFT JOIN来进行理解的。还是基于如下这样一个数据集： FruitName ProctPlace Price
Apple China $1.1
Apple Japan $2.1
Apple USA $2.5
Orange China $0.8
Banana China $3.1
Peach USA $3.0
首先我们不使用带ALL关键字的Group By语句： SELECT COUNT(*) AS 水果种类, ProctPlace AS 出产国 FROM T_TEST_FRUITINFO WHERE (ProctPlace <> 'Japan') GROUP BY ProctPlace 那么在最后结果中由于Japan不符合where语句，所以分组结果中将不会出现Japan。 现在我们加入ALL关键字： SELECT COUNT(*) AS 水果种类, ProctPlace AS 出产国 FROM T_TEST_FRUITINFO WHERE (ProctPlace <> 'Japan') GROUP BY ALL ProctPlace 重新运行后，我们可以看到Japan的分组，但是对应的“水果种类”不会进行真正的统计，聚合函数会根据返回值的类型用默认值0或者NULL来代替聚合函数的返回值。 2.3 GROUP BY [Expressions] WITH CUBE | ROLLUP： 首先需要说明的是Group By All 语句是不能和CUBE 和 ROLLUP 关键字一起使用的。 首先先说说CUBE关键字，以下是SQL Server 2000联机帮助中的说明： 指定在结果集内不仅包含由 GROUP BY 提供的正常行，还包含汇总行。在结果集内返回每个可能的组和子组组合的 GROUP BY 汇总行。GROUP BY 汇总行在结果中显示为 NULL，但可用来表示所有值。使用 GROUPING 函数确定结果集内的空值是否是 GROUP BY 汇总值。 结果集内的汇总行数取决于 GROUP BY 子句内包含的列数。GROUP BY 子句中的每个操作数（列）绑定在分组 NULL 下，并且分组适用于所有其它操作数（列）。由于 CUBE 返回每个可能的组和子组组合，因此不论指定分组列时所使用的是什么顺序，行数都相同。 我们通常的Group By语句是按照其后所跟的所有字段进行分组，而如果加入了CUBE关键字以后，那么系统将根据所有字段进行分组的基础上，还会通过对所有这些分组字段所有可能存在的组合形成的分组条件进行分组计算。由于上面举的例子过于简单，这里就再适合了，现在我们的数据集将换一个场景，一个表中包含人员的基本信息：员工所在的部门编号(C_EMPLINFO_DEPTID)、员工性别(C_EMPLINFO_SEX)、员工姓名(C_EMPLINFO_NAME)等。那么我现在想知道每个部门各个性别的人数，那么我们可以通过如下语句得到： SELECT C_EMPLINFO_DEPTID, C_EMPLINFO_SEX, COUNT(*) AS C_EMPLINFO_TOTALSTAFFNUM FROM T_PERSONNEL_EMPLINFO GROUP BY C_EMPLINFO_DEPTID, C_EMPLINFO_SEX 但是如果我现在希望知道： 1. 所有部门有多少人(这里相当于就不进行分组了，因为这里已经对员工的部门和性别没有做任何限制了，但是这的确也是一种分组条件的组合方式)； 2. 每种性别有多人(这里实际上是仅仅根据性别(C_EMPLINFO_SEX)进行分组)； 3. 每个部门有多少人(这里仅仅是根据部门(C_EMPLINFO_DEPTID)进行分组)；那么我们就可以使用ROLLUP语句了。 SELECT C_EMPLINFO_DEPTID, C_EMPLINFO_SEX, COUNT(*) AS C_EMPLINFO_TOTALSTAFFNUM FROM T_PERSONNEL_EMPLINFO GROUP BY C_EMPLINFO_DEPTID, C_EMPLINFO_SEX WITH CUBE 那么这里你可以看到结果集中多出了很多行，而且结果集中的某一个字段或者多个字段、甚至全部的字段都为NULL，请仔细看一下你就会发现实际上这些记录就是完成了上面我所列举的所有统计数据的展现。使用过SQL Server 2005或者RDLC的朋友们一定对于矩阵的小计和分组功能有印象吧，是不是都可以通过这个得到答案。我想RDLC中对于分组和小计的计算就是通过Group By的CUBE和ROLLUP关键字来实现的。(个人意见，未证实) CUBE关键字还有一个极为相似的兄弟ROLLUP, 同样我们先从这英文入手，ROLL UP是“向上卷”的意思，如果说CUBE的组合是绝对自由的，那么ROLLUP的组合就需要有点约束了。我们先来看看SQL Server 2000的联机中对ROLLUP关键字的定义： 指定在结果集内不仅包含由 GROUP BY 提供的正常行，还包含汇总行。按层次结构顺序，从组内的最低级别到最高级别汇总组。组的层次结构取决于指定分组列时所使用的顺序。更改分组列的顺序会影响在结果集内生成的行数。 那么这个顺序是什么呢？对了就是Group By 后面字段的顺序，排在靠近Group By的分组字段的级别高，然后是依次递减。如：Group By Column1, Column2, Column3。那么分组级别从高到低的顺序是：Column1 > Column2 > Column3。还是看我们前面的例子，SQL语句中我们仅仅将CUBE关键字替换成ROLLUP关键字，如： SELECT C_EMPLINFO_DEPTID, C_EMPLINFO_SEX, COUNT(*) AS C_EMPLINFO_TOTALSTAFFNUM FROM T_PERSONNEL_EMPLINFO GROUP BY C_EMPLINFO_DEPTID, C_EMPLINFO_SEX WITH ROLLUP 和CUBE相比，返回的数据行数减少了不少。:)，仔细看一下，除了正常的Group By语句后，数据中还包含了： 1. 部门员工数；(向上卷了一次，这次先去掉了员工性别的分组限制) 2. 所有部门员工数；(向上又卷了依次，这次去掉了员工所在部门的分组限制)。 在现实的应用中，对于报表的一些统计功能是很有帮助的。 这里还有一个问题需要补充说明一下，如果我们使用ROLLUP或者CUBE关键字，那么将产生一些小计的行，这些行中被剔除在分组因素之外的字段将会被设置为NULL,那么还存在一种情况，比如在作为分组依据的列表中存在可空的行，那么NULL也会被作为一个分组表示出来，所以这里我们就不能仅仅通过NULL来判断是不是小计记录了。下面的例子展示了这里说得到的情况。还是我们前面提到的水果例子，现在我们在每种商品后面增加一个“折扣列”(Discount)，用于显示对应商品的折扣，这个数值是可空的，也就是可以通过NULL来表示没有对应的折扣信息。数据集如下所示： FruitName ProctPlace Price Discount
Apple China $1.1 0.8
Apple Japan $2.1 0.9
Apple USA $2.5 1.0
Orange China $0.8 NULL
Banana China $3.1 NULL
Peach USA $3.0 NULL
现在我们要统计“各种折扣对应有多少种商品，并总计商品的总数。”，那么我们可以通过如下的SQL语句来完成： SELECT COUNT(*) AS ProctCount, Discount FROM T_TEST_FRUITINFO GROUP BY Discount WITH ROLLUP 好了，运行一下，你会发现数据都正常出来了，按照如上的数据集，结果如下所示： ProctCount Discount
3 NULL
1 0.8
1 0.9
1 1.0
6 NULL
好了，各种折扣的商品数量都出来了，但是在显示“没有折扣商品”和“商品小计”的时候判断上确存在问题，因为存在两条Discount为Null的记录。是哪一条呢？通过分析数据我们知道第一条数据(3, Null)应该对应没有折扣商品的数量，而(6,Null)应该对应所有商品的数量。需要判断这两个具有不同意义的Null就需要引入一个聚合函数Grouping。现在我们把语句修改一下，在返回值中使用Grouping函数增加一列返回值，SQL语句如下： SELECT COUNT(*) AS ProctCount, Discount, GROUPING(Discount) AS Expr1 FROM T_TEST_FRUITINFO GROUP BY Discount WITH ROLLUP 这个时候，我们再看看运行的结果： ProctCount Discount Expr1
3 NULL 0
1 0.8 0
1 0.9 0
1 1.0 0
6 NULL 1
对于根据指定字段Grouping中包含的字段进行小计的记录，这里会标记为1，我们就可以通过这个标记值将小计记录从判断那些由于ROLLUP或者CUBE关键字产生的行。Grouping(column_name)可以带一个参数，Grouping就会去判断对应的字段值的NULL是否是由ROLLUP或者CUBE产生的特殊NULL值，如果是那么就在由Grouping聚合函数产生的新列中将值设置为1。注意Grouping只会检查Column_name对应的NULL来决定是否将值设置为1，而不是完全由此列是否是由ROLLUP或者CUBE关键字自动添加来决定的。 2.2 Group By 和 Having, Where ,Order by语句的执行顺序： 最后要说明一下的Group By, Having, Where, Order by几个语句的执行顺序。一个SQL语句往往会产生多个临时视图，那么这些关键字的执行顺序就非常重要了，因为你必须了解这个关键字是在对应视图形成前的字段进行操作还是对形成的临时视图进行操作，这个问题在使用了别名的视图尤其重要。以上列举的关键字是按照如下顺序进行执行的：Where, Group By, Having, Order by。首先where将最原始记录中不满足条件的记录删除(所以应该在where语句中尽量的将不符合条件的记录筛选掉，这样可以减少分组的次数)，然后通过Group By关键字后面指定的分组条件将筛选得到的视图进行分组，接着系统根据Having关键字后面指定的筛选条件，将分组视图后不满足条件的记录筛选掉，然后按照Order By语句对视图进行排序，这样最终的结果就产生了。在这四个关键字中，只有在Order By语句中才可以使用最终视图的列名，如： SELECT FruitName, ProctPlace, Price, ID AS IDE, Discount FROM T_TEST_FRUITINFO WHERE (ProctPlace = N'china') ORDER BY IDE 这里只有在ORDER BY语句中才可以使用IDE，其他条件语句中如果需要引用列名则只能使用ID，而不能使用IDE。
❺ 数据库(比如MYSQL) ,表连结查询与子查询哪个效率高些 为什么
in子查询、exists子查询、连接，效率的探讨
以下是SQL的帮助 （高级查询优化概念）
Microsoft® SQL Server™ 2000 使用内存中的排序和哈希联接技术执行排序、交集、联合、差分等操作。SQL Server 利用这种类型的查询计划支持垂直表分区，有时称其为分列存储。
SQL Server 使用三种类型的联接操作：
嵌套循环联接
合并联接
哈希联接
如果一个联接输入很小（比如不到 10 行），而另一个联接输入很大而且已在其联接列上创建索引，则索引嵌套循环是最快的联接操作，因为它们需要最少的 I/O 和最少的比较。有关嵌套循环的更多信息，请参见了解嵌套循环联接。
如果两个联接输入并不小但已在二者联接列上排序（例如，如果它们是通过扫描已排序的索引获得的），则合并联接是最快的联接操作。如果两个联接输入都很大，而且这两个输入的大小差不多，则预先排序的合并联接提供的性能与哈希联接相似。然而，如果两个输入的大小相差很大，则哈希联接操作通常快得多。有关更多信息，请参见了解合并联接。
哈希联接可以有效处理很大的、未排序的非索引输入。它们对复杂查询的中间结果很有用，因为：
中间结果未经索引（除非已经显式保存到磁盘上然后创建索引），而且生成时通常不为查询计划中的下一个操作进行适当的排序。
查询优化器只估计中间结果的大小。由于估计的值在复杂查询中可能有很大的误差，因此如果中间结果比预期的大得多，则处理中间结果的算法不仅必须有效而且必须适度弱化。
哈希联接使得对非规范化的使用减少。非规范化一般通过减少联接操作获得更好的性能，尽管这样做有冗余之险（如不一致的更新）。哈希联接则减少使用非规范化的需要。哈希联接使垂直分区（用单独的文件或索引代表单个表中的几组列）得以成为物理数据库设计的可行选项。有关更多信息，请参见了解哈希联接。
❻ 为了测试数据库查询的效率是否提升,经常使用索引来实现,请问什么是索引 有什么作用 原理是什么
一、什么是索引？
索引就像是书的目录，是与表或者视图关联磁盘上的结构，可以加快从表中或者视图中检索行的速度。素银中包含表或者视图中的一行或者多列生成的键。这些键存储在一个结构（BTree）中，使SQL可以快速有效的查找与键值关联的行。
二、有什么用？即索引的优点
建立索引的行可以保证行的唯一性，生成唯一的word
建立索引可以有效的缩短数据的检索时间
建立索引可以加快表与表之间的 连接
为用来排序或者是分组的字段添加索引可以加快和排序顺序
无索引，直接去读表数据存放的磁盘快，督导数据缓冲区中再去查找需要的数据
有索引，先读入索引表，通过索引表直接去找到需要数据的物理地址，并把数据读入数据缓冲区中。
三、索引的原理
通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。
❼ SQL Server 聚集索引和非聚集索引的区别分析
聚集索引和非聚集索引的根本区别
聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致，聚集索引表记录的排列顺序与索引的排列顺序一致，优点是查询速度快，因为一旦具有第一个索引值的纪录被找到，具有连续索引值的记录也一定物理的紧跟其后。
聚集索引的缺点是对表进行修改速度较慢，这是为了保持表中的记录的物理顺序与索引的顺序一致，而把记录插入到数据页的相应位置，必须在数据页中进行数据重排，降低了执行速度。建议使用聚集索引的场合为：
a.此列包含有限数目的不同值；
b.查询的结果返回一个区间的值；
c.查询的结果返回某值相同的大量结果集。
非聚集索引指定了表中记录的逻辑顺序，但记录的物理顺序和索引的顺序不一致，聚集索引和非聚集索引都采用了B+树的结构，但非聚集索引的叶子层并不与实际的数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针的方式。非聚集索引比聚集索引层次多，添加记录不会引起数据顺序的重组。建议使用非聚集索引的场合为：
a.此列包含了大量数目不同的值；
b.查询的结束返回的是少量的结果集；
c.order by 子句中使用了该列。
--不用索引查询
Select * FROM IndexTestTable WHIT(INDEX(0)) Where Status='B'
--创建聚集索引
Create CLUSTERED INDEX icIndexTestTable ON IndexTestTable(Status)
--使用索引查询
Select * FROM IndexTestTable WITH(INDEX(icIndexTestTable)) Where Status='B'
表中经常有一个列或列的组合，其值能唯一地标识表中的每一行。这样的一列或多列称为表的主键(默认为聚集索引)。聚集索引确定表中数据的物理顺序。聚集索引类似于电话簿，后者按姓氏排列数据。由于聚集索引规定数据在表中的物理存储顺序，因此一个表只能包含一个聚集索引。但该索引可以包含多个列（组合索引），就像电话簿按姓氏和名字进行组织一样。
非聚集索引与课本中的索引类似。数据存储在一个地方，索引存储在另一个地方，索引带有指针指向数据的存储位置。索引中的项目按索引键值的顺序存储，而表中的信息按另一种顺序存储（这可以由聚集索引规定）。如果在表中未创建聚集索引，则无法保证这些行具有任何特定的顺序。
聚集索引就像我们新华字典中的按拼音排序，即你查"爱"字可以在前面看到"癌"字，但却不能在前后页中看到"受"字。而非聚集索引就是新华字典中的按部首、笔划排序。聚集索引相当于我们书本上前面的目录的一样，它可以方便快速的找到你想找的内容，而非聚集索引就相当于书最后几页的解释，它是对书中某个语句或者是生词的解释，就像我们上学时候的地理说一样，书后面都有各种地理名称的英文解释。
《数据库原理》里面的解释：聚集索引的顺序就是数据的物理存储顺序，而非聚集索引的顺序和数据物理排列无关。因为数据在物理存放时只能有一种排列方式，所以一个表只能有一个聚集索引。
在SQL SERVER中，索引是通过二叉树的数据结构来描述的；我们可以如此理解这个两种索引：聚集索引的叶节点就是数据节点，而非聚集索引的叶节点仍然是索引节点，只不过其包含一个指向对应数据块的指针。
聚集索引会降低 insert，和update操作的性能，所以，是否使用聚集索引要全面衡量。