函数功能：

指定的表的次序（循环条件中表示不同表位置的值递增）求解单表s与局部最优查询树的最优连接。

 

代码分析：

static void

optimize_straight_join(JOIN *join,
table_map join_tables)

{

……

  for
(JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)//遍历remaining_tables中的每个表s

  {

   
/*
Find the best access method from 's' to the current partial plan */

   
best_access_path(join, s, join->thd, join_tables, idx,

                     record_count, read_time);

//通过调用best_access_path函数得到局部查询计划的最优花费保存到“join->positions[idx].records_read”和“join->positions[idx].read_time”，然后计算当前最优花费（best_access_path函数体中的最后，为这2个变量赋值）

 

   
/* compute the cost of the new plan extended with 's' */

   
record_count*= join->positions[idx].records_read;

   
read_time+=   
join->positions[idx].read_time;

   
join_tables&= ~(s->table->map);

   
++idx; //保障下次调用best_access_path函数时，从本次循环使用的表s的下一个表的位置正确

  }

 

 
read_time+= record_count / (double) TIME_FOR_COMPARE;

……

 
join->best_read= read_time; //得到本次连接的最优花费

}

前言
该文章所用到的表结构：
SET FOREIGN_KEY_CHECKS=0;

-- ----------------------------
-- Table structure for svip
-- ----------------------------
DROP TABLE IF EXISTS `svip`;
CREATE TABLE `svip` (
  `vip_id` int(11) NOT NULL AUTO_INCREMENT COMMENT '会员编号',
  `vip_name` varchar(10) NOT NULL DEFAULT '' COMMENT '会员姓名',
  `vip_cardID` varchar(18) NOT NULL COMMENT '会员身份证号码',
  `vip_iphone` varchar(10) NOT NULL COMMENT '会员电话',
  `vip_address` varchar(50) NOT NULL COMMENT '会员住址',
  `vip_mark` text NOT NULL COMMENT '会员备注信息',
  PRIMARY KEY (`vip_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

来源
       MySQL索引用来快速地寻找那些具有特定值的记录，所有MySQL索引都以B-树的形式保存，如果没有索引，执行查询时MySQL必须从第一个记录开始扫描整个表的所有记录，直至找到符合要求的记录。表里面的记录数量越多，这个操作的代价就越大，如果作为搜索条件的列上已经创建了索引，$\color{#FF0000}{MySQL无需扫描任何记录即可迅速得到目标记录所在的位置}$。如果表中有1000个记录，通过索引查找记录至少要比顺序扫描记录快100倍。

在使用like的时候，如果使用‘%%’，会不会用到索引呢？
EXPLAIN SELECT * FROM svip WHERE vip_id LIKE '%1%'

查询结果possible_key为空，表示没有用到索引：



使用到了主键索引：



综上，MySQL在使用like查询的时候只使用后面的%时，才会使用到索引。
索引分类：

PRIMARY 主键：唯一且不能为空。

INDEX：普通的索引。

UNIQUE 唯一索引：不允许有重复。

FULLTEXT 全文索引：用于在一篇文章中，检索文本信息的。

各有什么区别？各适用于什么场合？

举个例子来说，比如你在为某商场做一个会员卡的系统，这个系统有一张会员表，表结构如上前言，各字段含义：

会员编号 INT

会员姓名 VARCHAR(10)

会员身份证号码 VARCHAR(18)

会员电话 VARCHAR(10)

会员住址 VARCHAR(50)

会员备注信息 TEXT
那么这个会员编号，作为主键，使用 PRIMARY

会员姓名如果要建索引的话，那么就是普通的 INDEX

会员身份证号码如果要建索引的话，那么可以选择 UNIQUE （唯一的，不允许重复）

会员备注信息如果要建索引的话，可以选择 FULLTEXT，全文搜索。

       不过 FULLTEXT 用于搜索很长一篇文章的时候，效果最好，用在比较短的文本，如果就一两行字的，普通的 INDEX 也可以。MySQL从3.23.23版开始支持全文索引和全文检索，在MySQL中，全文索引的索引类型为FULLTEXT。全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建。它可以通过CREATE TABLE命令创建，也可以通过ALTER TABLE或CREATE INDEX命令创建。对于大规模的数据集，通过ALTER TABLE（或者CREATE INDEX）命令创建，全文索引要比把记录插入带有全文索引的空表更快。
MySQL添加索引方法
索引算法：
       我们在MySQL中常用两种索引算法BTree和Hash，两种算法检索方式不一样，对查询的作用也不一样。

       BTree索引是MySQL数据库中最常用的索引算法，因为它不仅可以被用在=,>,>=,<,<=和between这些比较操作符上，而且还可以用于like操作符，只要它的查询条件是一个不以通配符开头的常量。

       Hash索引只能用于对等比较，例如“=”,“IN”,“<=>”（等价于=）操作符。由于是一次定位数据，不像BTree索引需要从根节点到枝节点，最后才能访问到页节点这种多次访问，所以检索效率远高于BTree索引，但Hash索引仅仅能满足“=”,“IN”,“<=>”查询，不能使用范围查询。

$\color{#FF0000}{Btree索引效率远小于Hash索引，但作用范围广，只要不是前置通配符即可使用。}$

例如这样也使用了索引：



Hash索引的几个缺点以至于工作中不经常使用：


Hash索引仅仅能满足“=”,“IN”,“<=>”查询，不能使用范围查询
联合索引中，Hash索引不能利用部分索引键查询
Hash索引无法避免数据的排序操作
Hash索引任何时候都不能避免表扫描
Hash索引遇到大量Hash值相等的情况后性能并不一定会比BTree高


小知识：

"<=>"符号其实在数学中叫做“等价于”，代表”推理中左边可以推出右边，右边也可推出左边”的意思，P=>Q：若P则Q，P<=Q：若Q则P，P<=>Q：若P则Q且若Q则P。接下来看一下我的测试，在库中建一张test表，建一个hash索引num1_hash。

表结构跟数据：
SET FOREIGN_KEY_CHECKS=0;

-- ----------------------------
-- Table structure for test
-- ----------------------------
DROP TABLE IF EXISTS `test`;
CREATE TABLE `test` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `num1` int(11) DEFAULT NULL,
  `num2` int(11) DEFAULT NULL,
  `num3` decimal(14,2) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `num1_hash` (`num1`) USING HASH
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8 COLLATE=utf8_bin;

-- ----------------------------
-- Records of test
-- ----------------------------
INSERT INTO `test` VALUES ('1', '1', '1', '1.00');
INSERT INTO `test` VALUES ('2', '2', '2', '2.00');
INSERT INTO `test` VALUES ('3', '3', '3', '3.00');
INSERT INTO `test` VALUES ('4', '4', '4', '4.00');
INSERT INTO `test` VALUES ('5', '5', '5', '5.00');

查询结果：



接下来再看看hash索引对<，<=，>，>=符号是否支持：









可以看出在<=2与<3是能命中索引的，在<=3与<4是全表扫描，所以<,>等符号也不是完全不能命中索引，跟btree测试结果一样，但是对查询的优化有没有用还没有研究过，后续会继续研究一下进行补充。

一.顺序查找

在链表中常用，适合用来解决小规模数据，比较灵活简便。当数据较多时非常不推荐，查询速度非常慢。



二. 二分查找



2.1 二分查找简介：

通过将一组有序数据不断地分成两部分以缩小查询区间的查询方法 

使用条件：数据有序



2.2二分查找的特点：

二分查找法优点是比较次数少，查找速度快，平均性能好，占用系统内存较少



2.3 二分查找的查询方式及其原理：



二分查找的查询步骤：

步骤一：检查表中间数据是否是目标数据，不是则继续向下执行 

步骤二：利用中间位置记录将表分成前、后两个子表，如果中间位置记录的数据大于目标数据，则查找前一子表，否则查找后一子表 

步骤三：重复以上过程，直到找到满足条件的数据，或直到子表不存在为止，则查找不成功



二分查找的查询原理：

下面举一个简单的例子，和此例的查找过程的流程图

问题： 

一个含有10个元素的有序数组Array 

Array的元素为：2，3，9，15，30，42，47，53，86，100 

查找Array数组，确定47是否在数组中，若在数组中，返回其在数组中的位置

二分法查找过程：





2.4 二分查找实现：



方式一：使用while循环实现




template <typename Type>
int ArrayList<Type>::BinarySearch(Type x) {
    int min = 0;
    int max = currentsize;
    int mid = min + (max - min) / 2;
    cout << mid << endl;
    //注意这里是小于等于，没有等于号会出现重大错误
    while (min <= max)
    {
        if (elements[mid] == x) {
            cout << "目标元素是顺序表中的第" << mid+1 << "个元素" << endl;
            return mid;
        } 
        else if (elements[mid] < x) {
            min = mid + 1 ;
            mid = min + (max - min) / 2;
            cout << mid << endl;
        }
        else if (elements[mid] > x) {
            max = mid - 1 ;
            mid = min + (max - min) / 2;
            cout << mid << endl;
        }
    }
    cout << "目标元素不在顺序表中" << endl;
    return -1;

}

测试方法即执行结果：



int main() {
    //定义一个顺序表
    ArrayList<int> test(7);
    //创建一个有序数组
    int array[7] = {1,2,3,4,5,6};
    //将数组中的值拷贝到顺序表中
    for (int i = 0; i < 6; i++){
        test.Insert(array[i],i);
    }
    test.Print();

    //分别查询3，6，1，5，4
    test.InterpolateSearch(3);
    test.InterpolateSearch(6);
    test.InterpolateSearch(1);
    test.InterpolateSearch(5);
    test.InterpolateSearch(4);

    //程序暂停
    cin.get();
    return 0;
}

执行结果：





方式二：使用递归实现



template <typename Type>
int ArrayList<Type>::BinarySearch(Type x,int min,int max) {
    int mid = min + (max - min) / 2;
    if(elements[mid] == x){
        cout << "目标元素是顺序表中的第" << mid+1 << "个元素" << endl;
        return mid;
    }else if(elements[mid] < x){
        BinarySearch(x ,mid+1 ,max);
    }else if(elements[mid] > x){
        BinarySearch(x ,min ,mid-1);
    }
    cout << "目标元素不在顺序表中" << endl;
    return -1;

}



三. 插值查找

在二分查找的基础上做了改进，比二分查找的速度更快



3.1 插值查找对二分查找的改进：

二分查找是每次将目标区域缩小二分之一，而插值查找通过修改比例，每次查找将目标区域缩小缩小了更多 

插值查找在实现方式上与二分查找的不同体现在mid中值的确定方面： 

二分查找：



mid = min + (max - min) / 2;

插值查找：



mid = min + (max - min)*1.0*(x - elements[min]) / (elements[max] - elements[min]);

注意：由于C/C++的int类型的截断取整特性，所以在乘以比例之前先要乘以浮点数1.0



3.2 插值查找的循环方式实现：



//插值查找
template <typename Type>
int ArrayList<Type>::InterpolateSearch(Type x) {
    int min = 0;
    int max = currentsize;
    int mid = min + (max-min)/2;
    cout << mid << endl;
    while (min <= max)
    {
        if (elements[mid] == x) {
            cout << "目标元素是顺序表中的第" << mid + 1 << "个元素" << endl;
            return mid;
        }
        else if (elements[mid] < x) {
            min = mid + 1;
            mid = min + (max - min)*1.0*(x - elements[min]) / (elements[max] - elements[min]);
            cout << mid << endl;
        }
        else if (elements[mid] > x) {
            max = mid - 1;
            mid = min + (max - min)*1.0*(x - elements[min]) / (elements[max] - elements[min]);
            cout << mid << endl;
        }
    }
    cout << "目标元素不在顺序表中" << endl;
    return -1;
}

序言： 致每一位读者：你们好！ 我叫 Changlon [昌龙] ；  是和各位一样奔跑在编程道路上，期望 用编程改变世界，改善生活的奔跑者。


写文章的初心: 方便以后复习，方便未来面试，结交更多道友，交流心得经验…


如果你也对 前端 , Java , C/C++, 算法, 人工智能 感兴趣那就关注我吧！我们一起学习进步！

相关文章

点击查看 MySQL系列文章
联合查询
语法：

select 查询列表    ⑦

from 表1 别名       ①

连接类型 join 表2   ②

on 连接条件         ③

where 筛选          ④

group by 分组列表   ⑤

having 筛选         ⑥

order by排序列表  ⑧

limit 起始条目索引，条目数;  ⑨


 由于本人技术水平有限，博客中难免出现的一些错误，有纰漏之处恳请各位大佬不吝赐教！