確實設置了一個列索引在mysql表中確保O（1）查找？

所以當列上有一個索引，並且你做了一個簡單的SELECT * FROM table WHERE indexed_column = value，那麼這是一個O（1）搜索嗎？索引的內容是整數還是字符串是否重要？確實設置了一個列索引在mysql表中確保O（1）查找？

2011-10-06 tipu

潛在的問題是：是什麼使索引查找O（1）操作？這將取決於索引存儲的內部實現，我想... –

MySQL的MyISAM或InnoDB存儲引擎中的查找都不是O（1）搜索。那些存儲引擎使用B +樹來實現索引。他們能做的最好的是O（日誌 n）搜索。

MEMORY存儲引擎默認使用HASH索引類型，以及B +樹索引類型。只有HASH索引可以實現O（1）查找。

無論哪種情況，索引列的數據類型都不會更改它。

2011-10-06 22:43:51

MySQL使用B-Tree而不是Binary-Tree。它的複雜程度取決於每個節點的條目數量。關於MySQL，這裏描述了這裏（http://use-the-index-luke.com/sql/anatomy/the-tree） –

事實並非如此。

MySQL使用B-Trees，如online book中所述。它們的複雜性取決於每個節點的密鑰數量，因此可以比O（log2n）做得更好。

MySQL使用的每個節點的密鑰數取決於question中指出的不同因素。

2017-09-23 09:54:22

回答