数据库索引
本文大部分内容来自数据库系统概念(Data System Concepts)一书以及mooc上数据库系统战德臣老师的课程，这里只是自己加上自己的一些思考总结下笔记
一、基本概念
建立数据库索引的原因：当对于数据库的许多查询只涉及文件中很少一部分记录时。为了减少查找这些记录的开销，我们可以为存储数据库的文件创建索引。
例如:类似于“找出Perryridge分支机构的所有账户信息”或者“找出账号为A-101的余额”的查询，这种查询只涉及所有账户记录中的一小部分，如果系统读取所有的记录并一一检查branch_name字段值为“Perryridge”的记录，或者检查account_number字段找出值为“A-101”的记录，这样的操作方式是低效的。理想情况下，系统应该能够直接定位这些记录，为了实现这种访问数据的方式，设计出了附加结构并将其与数据库的文件关联起来，这种附加结构被称为“索引”。
索引的分类有两种：顺序索引和散列索引，顺序索引是基于值的有序序列，散列索引是基于将值均匀分布在若干个散列桶当中，一个值所示的散列桶是由一个函数决定的，该函数被称为散列函数。
评价不同的索引技术的指标主要有：访问类型(找到具有特定属性值的所有记录与在某个特定范围的所有记录)、访问时间(找到一个特定数据项或者数据项集)、插入时间(找到插入的正确位置的时间+更新索引结构的时间)、删除时间(找到待删除数据项位置的时间+更新索引结构的时间)、空间开销(索引结构额外占用的存储空间)。
搜索码：用于在文件中查找记录的属性或属性集。如果在一个文件有多个索引，那么它就有多个搜索码。
二、顺序索引
聚集索引或主索引：包含记录的文件内部是按照某个搜索码指定的顺序对所包含记录进行排序的(即11.7中的顺序文件组织)，那么该搜索码对应的索引称为聚集索引。也被称为主索引，但这里的主索引并不是单指建立在主码上的索引，而是可以建立在任何前面条件的搜索码上，虽然通常是主码。
非聚集索引或辅助索引：搜索码指定的顺序与文件中的记录的物理顺序不同的索引。
索引项或者索引记录：由一个搜索码值和指向该搜索码值的一个或者多个记录的指针构成。指向记录的指针包括磁盘块的标识和记录在标识磁盘块内的块内偏移量
1. 稠密索引和稀疏索引
稠密索引：文件中的每一个搜索码值有一个索引记录，稠密索引可能是聚集的也可能是非聚集的。这里的搜索码值可以有重复的，但对于聚集索引而言，在实现上没有必要是重复的，指向具有该搜索码值的第一个数据记录即可。
稀疏索引：只为搜索码的某些值建立索引记录，稀疏索引只能是聚集的。与聚集稠密索引一样，每个索引记录也包括了一个搜索码值和一个指向具有该搜索码值的第一个数据记录的指针。为了定位一条记录，我们找到其最大搜索码值和指向具有该搜索码值的第一个数据记录的指针。为了定位一条记录我们找到小于等于所找记录搜索码值的最大搜索码值对应的索引项，然后从该索引项的指向的记录开始，沿着文件中的指针查找，直到找到所需的记录为止。
稀疏索引与稠密索引的比较：通常利用稠密索引可以比稀疏索引更快地定位一条记录。但是稀疏索引也有比稠密索引优越的地方：所占空间小，并且插入和删除时的维护开销也较小。系统设计者必须在存取时间和空间开销之间进行权衡，但是为每个块建一个索引项是一个较好的折中，原因在于，处理数据库请求的开销主要由把块从磁盘中读入到主存当中的时间决定。一旦将块放入主存，扫描整个块的时间是可以忽略的(对应于稀疏索引从索引项指向的记录开始，沿着文件中的指针查找，直到找到所需的记录的时间是可以忽略的)。使用这样的稀疏索引，可以定位包含我们要查找的记录的块。这样，只要记录不在溢出块(11.7.1)，就能使块访问次数最小，同时能保持索引尽可能的小(因而减少了空间开销)。
2. 多级索引
多级索引(建立在成块稀疏索引之上的)：当数据量比较大时，索引本身即使是采取了(成块)稀疏索引也还是会变得非常大难以有效处理。
如对于一个10w条记录的文件，假设一个磁盘块能存储10条记录，如果每个块有一个索引记录那么索引就有1w条记录。索引记录比数据记录小，假设一个磁盘块能容纳100条索引记录。这样，索引将占据100个磁盘块。这样大的索引如在主存中放不下那么就必须以顺序文件的方式存储在磁盘上。这样即使在索引文件上使用二分查找来定位索引项，搜索的开销依然很大(如索引占据b个磁盘块，二分搜索需要读取log2b(向上取整)次)，对于有100块的索引，二分查找需要7次读索引块操作(这里指的是最坏情况下50+25+12+6+3+1+2)。如果使用了溢出块那么就不能使用二分查找，而是使用的顺序搜索，最坏情况下需要b次。
为了解决这种对于大量记录下读块次数过多的问题，出现了多级索引，即在成块的稀疏索引(内层索引)上再建立稀疏索引，被称为外层索引。比如还上面那个例子，为了我们已经建立100个索引块(1w条索引项)来指向所有记录所在块(1w块)，那再建立一个针对这100个索引块的外层成块稀疏索引，很明显只要1个索引块就够了，这一个索引块能够放到内存当中。这样的话我们就只需要1次读索引块(根据外层索引块所确定的那个内层索引块)的操作就能找到特定记录所在的磁盘块了。如果外层索引块依然是太大不能放到主存当中，那就继续对其建立上级索引，直到最外层索引能够放到主存当中。
无论采用何种形式的索引，每当文件中有记录插入或者删除时，索引都需要更新。系统根据索引时稠密索引还是稀疏索引而进行下一个操作。更新的算法具体看书上P321页。
3. 辅助索引
辅助索引即非聚集索引必须是稠密索引，为了避免稠密索引出现重复值，可以采取指针桶的办法，将对应同一个搜索码值的记录的指针都放到同一个指针桶当中，再用搜索码值对应的索引项指向这个指针桶
三、B+树索引
索引顺序文件组织的最大缺点在于，随着文件的增大，索引查找性能和数据顺序扫描性能都会下降这里讲的是单级的索引顺序文件，缺点:1.在介绍多级索引时也说了需要的IO次数是与索引磁盘块成对数关系的，这里的解决方法就是采取多级索引，B+树就是一种多级索引；2.并且对于出现在溢出块当中的还必须顺序查找就更慢了，这里的严格地说是存放记录的文件组织方式即顺序文件组织造成的，因为当块满了的时候，它会将记录放到溢出块中，就不能使用顺序查找了。这个问题的解决就是用到了后面讲到的B+树文件组织方式，虽然这种性能下降可以通过对文件进行重新组织来弥补，但是我们不希望频繁地进行重组。这里弥补的是第二点，把溢出块中的记录整理回排序块了，避免了出现顺序查找。书上说的是有溢出块出现不能使用二分查找了，个人理解是在还是可以的，找到对应记录块中然后通过指针就能继续找到溢出块中的记录了，只不过是还要再多IO一次把对应的溢出块加载进来然后找到，还是没太弄清楚教材上为什么说只能顺序查找。
B+树的查询插入删除更新操作原理结合可视化数据结构
1. 查询操作
procedure find(value V)
设置C=根节点
while C不是叶节点 begin
找到大于V的最小搜索码值Ki(如果有的话)
if 没有这样的值 then begain
令m=结点中指针的数目
设置C=Pm指向的结点
end
else 设置C=Pi指向的结点
end
if C中有一个码值Ki,满足Ki=V
then 指针Pi指向我们需要的记录或指针桶
else 不存在具有码值为k的记录2. 插入操作
procedure insert(value K,point P)
找到应该包含值K的叶节点L
if(L所含搜索码少于n-1个)
then insertInLeaf(L,K,P)
else begin //L已经含有n-1个搜索码了，分裂L
创建结点L'
把L.P1,...,L.Kn-1复制到可以存储n个(指针,搜索码)对的内存块T//注意这里是n对所以能把K也放进去了
insertInLeaf(T,K,P)
令L'.Pn=L.Pn;令L.Pn=L'//原来的L变成了L+L'
把T.P1,...,T.K⌈n/2⌉从T复制到L中，以L.P1作为开始
把T.P⌈n/2⌉+1,...,T.Kn从T复制到L'中，以L'.P1作为开始
令K'表示L'中最小搜索码值insertInParent
insertInParent(L,K',L')
end
procedure insertInLeaf(node L,vlaue K,pointer P)
if K比L.K1小
then 把P,K插入到L中，紧接L.P1前面
else begin
令Ki表示L中小于K的最大搜索码值
把P,K插入L中,紧接T.Ki后面
end
procedure insertInParent(node N,vlaue K',node N')
if N是树的根节点//通过父指针是不是null来判断
then begin
创建新结点R包含N、K'、N' //N和N'都是指针
令R成为树的根节点
return
end
令P=parent(N)
if(P包含的指针少于n个)
then 将(K',N')插到P中N后面
else begin //分裂P
将P复制到可以存放P以及(K',N')的内存块T中
把结点(K',N')插入T当中，紧跟在N后面
删除P中所有项；创建结点P'
把T.P1,...,T.P⌈n/2⌉复制到P
令K''=T.K⌈n/2⌉
把T.P⌈n/2⌉+1,...,T.Kn复制到P'
//所有的指针都保留下来了，搜索码值仅有两节点的分割点T.K⌈n/2⌉未保留，但是传到父结点当中了
insertInParent(P,K'',P')
end3. 删除操作
伪代码待补充
四、B+树扩展
1. B+树组织文件
教材和PPT上在起初介绍都是将叶子节点中存放的是搜索码值和搜索码值对应记录的指针，但在Mysql当中(其他数据库还未确定，但这种应该是使适用的)叶子节点存放的直接就是对应的记录了(按聚簇索引搜索码排序)，并不需要再弄个指针去指向记录所在的位置)。
但这点其实教材数据库系统概念在P330上也有说，这种用来解决存储实际记录的性能下降问题(溢出块造成)，即在树中叶子节点存储实际记录而不是指向记录的指针的方式就被称为B+树文件组织。
注意B+树索引或B+树文件组织中，树中相邻的叶节点可能分布在磁盘中的不同位置。当一个文件组织最初在建立一组记录上的伤害，可以把磁盘上基本连续的块分配给树中连续的叶节点(这样就不光逻辑上是连续的，物理上也是连续的，比如多个磁盘块或者磁盘页可能就在一个磁道上，减少了寻道时间)。由此，对叶节点的顺序扫描也就几乎是顺序的扫描。随着树中不断进行插入和删除操作，这种顺序性逐渐丢失，对叶节点的顺序访问也仅只是逻辑上连续，在物理存储上也需要越来越频繁地等待磁盘寻道。为了恢复这种物理连续性，也许需要对索引进行重建。具体可看索引重建(重组)的常见问题。
- 扇区： 硬盘的最小读写单元
- 块/簇： 是操作系统针对硬盘读写的最小单元
- page： 是内存与操作系统之间操作的最小单元。
扇区 <= 块/簇 <= 页
我们都知道计算机在存储数据的时候，有最小存储单元，这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k，而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K。
2. 辅助索引(二级索引)和记录重定位
看到了关于MySQL当的中聚集索引与二级索引的术语说法，查了半天各种博客也没说出来这个二级索引到底是个什么东西？后面找到了官方页面的解释才算清楚Clustered and Secondary Indexes。ps：其实二级索引就是非聚集索引(辅助索引)，聚簇索引就是聚集索引。
聚簇索引在Mysql中指的是对于每一张表有且仅有一个索引，当在建表的时候定义了主键的时候，那么InnoDB就是将这个主键作为聚簇索引的搜索码来生成索引，如果未定义主键但表中有唯一键并且唯一键值当中没有null存在的话就把这个唯一键作为聚簇索引的搜索码(或者叫关键字、索引键等等)，如果连这样一个唯一键都还找不到的话，那么InnoDB则会隐式的给你根据6字节大小行ID作为搜索码来生成一个聚簇索引，这个行ID是你在插入记录的时候InnoDB自动递增地给赋的值。聚簇索引也就是数据库系统概念上的聚集索引，选择了什么字段作为搜索码，那么在InnoDB表数据文件都是基于这个搜索码进行顺序组织的。也就是说对于采用行ID作为搜索码而言的聚簇索引，其表中的记录的物理存储就是按照插入顺序排序的。这样的聚簇索引是采用B+树来实现的
在MySql当中建立索引是基于上面的那个聚簇索引的，即在辅助索引的非叶子结点那一层所包含的是按辅助索引搜索码排好序的一个个索引块，里面除了有辅助索引的搜索码值外还有搜索码值对应的该表的聚簇索引的搜索码值，这样我们也能通过B+树来实现了辅助索引，但我们最后得到并不再直接是对应的记录了，而是一个表的聚簇索引的搜索码值，再根据这个搜索码值去聚簇索引的B+树当中去找到对应的记录即可。所以一般说主键不要设置的的太长，因为一旦建立了辅助索引所有主键都复制一份的，主键过长就会导致占用空间较多，当有多个辅助索引时情况更严重。关于IO次数，这样算下来是两次B+树查询IO次数也不过是2倍的树高，在Mysql中一般就是2-6而已。
至于为什么辅助索引当中不直接存放指向记录的指针呢，原因可以参看由浅入深理解索引的实现或者教材P334页12.5.5辅助索引和记录重定位：一些文件组织如B+树文件组织可能改变记录的位置，Mysql聚簇索引采用的正是B+树 ，即使记录并没有更新。举例来说，当B+树文件组织中的一个磁盘页被分裂，一些记录会被移到新的磁盘页。在这种情况下，所有存储了定向重定位的记录的指针的辅助索引必须更新，即使记录中的值并没有改变。每个磁盘页可能包含相当多的记录，而其中每个记录度可能被分配到每个辅助索引上的不同位置，。因此一次叶磁盘页的分裂可能需要几十甚至几百次IO操作来更新所有影响到的辅助索引，导致这个操作代价及其高昂，为了解决这个问题，采用的方法就是在辅助索引当中，我们不存储指向索引记录的指针，而是存储主索引(聚簇索引)的搜索码属性的值。
3.一棵三层B+树可以存放多少行数据
InnoDB一棵B+树可以存放多少行数据？这篇文章以InnoDB中的三层B+树能放多少行数据做出了详细清楚的解答。其实就是先根据聚簇索引搜索码字段长度Lm、指向磁盘页的指针长度Lp(默认6B)、磁盘页的大小L(默认16K)根据(n-1)Lm+nLp<=L得出最大的n,那么就最多能指向n^2叶节点个磁盘页，再根据一条记录大小Lr,根据mLr<=L算出最大的m，就得出了最大的记录数mn^2