堆（heap）结构比较于B树的优缺点是什么?

一、堆（heap）结构比较于B树的优缺点

堆（heap）结构比较于B树的优缺点是堆只能访问一个元素，也就是堆顶，其他的元素在堆里是无意义的。优点也是这个，既然用堆了，那就是想访问堆顶，查询复杂度O(1)。B树每个节点都有意义，但访问特定的元素要进行中序遍历，肯定比堆慢。

堆

堆（heap）组织表数据行在堆中存储，没有任何特定顺序，向一个全新的没有做过更新和删除的堆中插入一行时候，总是 append 到堆表文件的最后一页当中。因为不用考虑排序，所以插入速度会比较快。

但是要查找符合某个条件的记录，就必须得读取全部的记录以便筛选。而这个时候为了加快查询速度，索引就出现了，索引是针对少量特定字段的值拿出来进行排序存储，存储索引 key 以及数据行在堆表上面的绝对位置（页号，页内偏移），而因为索引是有序的，所以就会很容易通过索引查询到具体的记录位置（普遍使用二分查找法），然后再根据记录位置直接从表中读取该记录。同时因为索引的字段较少，所以索引通常会比其基表小得多。

从上面通过索引访问表记录的方式可以看出，当要访问的数据量较大时，通过每一条记录的位置去访问原始记录，每一条符合条件的记录都需要经过索引访问后再访问基表这样一个复杂的过程，这会花费很多时间。同样，如果不经过索引而直接查询表，也可能因为表字段太多，记录较大的情况下把全部的数据读取进来，这也会花费很多时间。

那怎么办呢？这个时候就会想到，如果表中数据本身就是有序的，这样查询表的时候就可以快速的找到符合条件的记录位置，而很容易判断符合条件记录的位置，这样只需要读取一小部分数据出来就可以了，不需要全表记录都读取出来进行判断。索引组织表就这样产生了，当然索引表中插入，更新的时候可能会因为需要排序而将数据重组，这时候数据插入或更新速度会比堆组织表慢一些。如果堆组织表上有索引，那么对堆组织表的插入也会因为要修改索引而变慢。

由于堆表的索引只存储索引 key 以及数据行在堆表上面的绝对位置（页号，页内偏移），如果这行记录发生了更新，并且不能原地更新，需要进行迁移，那么就会发生一个情况，堆表所有索引都需要修改，指向新的行位置。而索引组织表就不需要这个开销，更新只会新插入变化了的索引 key，不变的索引 key 不需要新插入，只有当主键发生更改才需要对应修改其他二级索引，通常主键也不会更新，所以这也就是索引组织表更新效率更高的由来。

但一般使用堆表的数据库都不会直接这么更新，代价太大了。而是会在数据页预留一些空间，当遇见不能原地更新的记录时，就会在这个页中新插入一条更新后的记录，然后在这个页中做一个指针把老记录指向新纪录，这样就不用更新索引信息了。当然，如果你这个页中没有空闲空间可以插入新的记录，那么还是需要做行迁移，然后更新所有索引。

延伸阅读：

二、堆表和索引组织表的比较

堆表的特点就是索引和数据分开，所有索引都是二级索引，或叫辅助索引。所以主键索引也是二级索引，没有完整记录，区别只有少数或非少数。索引中存储的是 key 与指针，指针指向具体数据记录。当然，查找 key 的算法都是一样的，使用二分查找，也叫书签查找。

跟索引组织表相比，堆表有什么好处呢？其实主要就是通过主键或二级索引查询，开销是一样的。都是通过先找到key，然后定位到数据。而索引组织表，由于二级索引是指向主键，所以查询二级索引需要先定位到 key，然后拿到主键 id，还要根据主键 id 再次通过二分查找定位到真正的数据页。当然，索引组织表通过主键查询开销与堆是一样的。从索引组织表的工作方式可以看出，索引组织表必须要有主键，如果非显式创建，InnoDB 存储引擎会默认创建一个 ROWID 当做主键；而堆表则无强制要求。