MySQL为何选择B+树存储索引
MySQL为何选择B+树存储索引
声明
本文所述的各种数据结构(二叉树等)，均不考虑重复值的情况，本文简述各种数据结构的区别仅仅只是为了理解MySQL索引的需要而做的铺垫。
什么是索引
提起索引，大家都知道，建立索引可以让数据库查询更快，那么索引究竟是什么？我想这就不是每个人都能说得出来了。
索引，是数据库管理系统中一个排序的数据结构，并用以协助快速查询、 更新数据库表中数据。
是的，索引是一种数据结构，但是那么多的数据结构中为何MySQL要选择B+树呢？接下来就让我们一起来了解下B+树相对于其他数据结构有何独特之处！
二分查找法(Binary Search)
首先让我们自己想一想，如果让我们去设计，我们会怎么去存储？我想大部分人想到就是用链表或者数组去存储数据，然后再按默认的顺序排好，再去查找，而一个排好顺序的链表我们就可以通过二分查找法来高效查询。
二分查找也称折半查找，是一种效率较高的查找方法。比如有1-10十个数，我们要找到8，先从中间开始找5，然后发现8比5大，可以把5左边的数去掉，剩下6-10，再从中间开始找，依次类推，直到找到8为止。但是这种查找法有一个前提是数据必须是有序的，而且这种属于链表式的存储，我们一但要插入或者修改一个数据，可能会伴随着大量的下标移动，比如我们把1-10放在数组里面，下标分别对应0-9，然后现在要插入一个0，为了保证有序，0必须排在第一位，那么1-10所有的数据下标都要往后移动一位，这种就有点大动干戈了，所以为了解决这个问题，我们就有了二叉树。
二叉查找树(BST）
二叉查找树简称二叉树(BST)，英文全称：Binary Search Tree，这是一种什么样的数据结构呢？请看下图
在上面这棵树中，我们要找到8，先从根节点6开始比较，发现8比6大，就往右边走，就可以找到8
Trie树,前缀树
[TOC]
trie树，又叫前缀匹配树，适合做自动补全 和 敏感词过滤。它的key都为字符串，能做到高效查询和插入，时间复杂度为O(k)，k为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。
它的核心思想就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即「用空间换时间」，再利用共同前缀来提高查询效率。
时间轮算法
C 程序设计语言-读书笔记
[TOC]
《C 程序设计语言》。C语言经典版本。必读。 语法之外，主要是1988年出的ANSI标准。
学习一门语言。语法：1%， 标准库：10%， 惯用法：5%， 其他：84%。
导言
C语言通用规则： 在允许使用某种类型变量值的任何场合，都可以使用该类型的更复杂的表达式。
修改"20"等不明其意的幻数的方式是定义一个有意义的名字。
#define 名字 替换文本 # 注意，这里没有分号。。。#define 指令行末尾没有分号。
标准库提供的输入/输出模型非常简单。无论文本从何处输入，输出到何处，其输入/输出都是按照字节流的方式处理。
字符在机器内部是以
位模式出现的。char类型专门存储这类数据。getchar() 返回值之所以是int, 是因为EOF是个特殊的int, 在我的mac上是-1。在windows上Ctrl+Z输入EOF, 在mac上是Ctrl+D。
go 命令行参数解析
[TOC]
go标准库-flag
命令行的风格
由于一些历史原因，Unix 出现过很多不同的分支，命令行的风格也因此有很多标准，比如：
- Unix 风格，选项采用单 - 加一个字母，比如 -v，短选项就是它，优点是足够简洁;
- BSD 风格，选项没有 -，没有任何的前缀;
- GNU 风格，采用 --，如 --version，长选项，扩展性好，但是要多打几个字母;
查看系统进程有两种写法：
ps aux（BSD 风格） 和 ps -elf（Unix 风格）。
POSIX 的命令行风格算是取长补短的集合吧。什么是 POSIX 风格？可以查看这篇文档命令参数语法。它同时提供了长短选项的标准。