是什么影响了数据库索引选型？

根据B-Tree的定义，可知检索一次最多需要访问h（B-Tree的高度）个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。但是逻辑上存储在一个页里并不代表物理上也存储在一个页里，为了达到这个目的，每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O，因为根节点会常驻内存。复杂度为O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。所以B-Tree作为索引结构效率是非常高的。这也是为什么数据库不选用红黑树作为索引（数据结构）的原因，一是因为红黑树的高度h要大的多；二是红黑树节点在物理上可能是单独存储的，无法利用局部性原理。复杂度为O(h)，效率明显比B-Tree差的多。

B+Tree分析：

上B+Tree更适合索引。究其原因，一是因为B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能；二是因为所有叶子节点形成有序链表，便于范围查询；所有的查找最终都会到叶子节点，从而保证了查询性能的稳定。

【编辑推荐】

1. DB-Engines 8 月数据库榜单，Oracle 受新版本策略影响
2. 教你如何破解数据库密码？
3. PostgreSQL走势凶猛，Oracle飙涨得益于新版本发布计划？| 8月数据库排行榜
4. Java高级编程——MySQL索引实现及优化原理解析
5. 区块链和数据库技术到底有何区别？

（编辑：张掖站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!