innoDB indexes
https://dev.mysql.com/doc/refman/5.7/en/innodb-indexes.html
B-tree index & hash index
选择b-tree的原因：支持磁盘， 且访问磁盘数据时间复杂度为o(log(H))
https://en.wikipedia.org/wiki/B-tree
the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as discs. It is commonly used in databasesand file systems.
b-tree 适合于存储系统，常被用于数据库和文件系统；
B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red-Black Trees), it is assumed that everything is in main memory. To understand the use of B-Trees, we must think of the huge amount of data that cannot fit in main memory. When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time.
b-tree是个自平衡tree，
The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations (search, insert, delete, max, min, ..etc ) require O(h) disk accesses where h is the height of the tree. B-tree is a fat tree. The height of B-Trees is kept low by putting maximum possible keys in a B-Tree node.
使用 B-Tree的主要目的就是 以 o(log(h))的时间复杂度来 查找、删除、添加数据；b-tree结构的数据存放在磁盘上， 也就是以 0(log(H))的时间复杂度，在磁盘上获取数据；
Generally, a B-Tree node size is kept equal to the disk block size. Since h is low for B-Tree, total disk accesses for most of the operations are reduced significantly compared to balanced Binary Search Trees like AVL Tree, Red-Black Tree, ..etc.
B-Tree的深度h，相比于 AVL tree, Red-Black tree 来说较小， 进一步降低了 disk access（磁盘访问）次数；
网友评论