我在其他地方读到NSMutableArray有几种不同的实现方式，这取决于大小，有时实现为2-3树，而不仅仅是内存中的数组。这意味着，像删除对象这样的操作并不像必须将数组的整个尾部复制一个那么昂贵。
我想知道是否有一个快速的实现摘要，这样我就不必深入研究源代码了。
- 数组是如何排序的?
- 根节点在数组的中间吗?
- 数组如何找到第n个元素?
- 还有其他优势吗将数组实现为2-3树而不是快速移除靠近数组前面的对象?
搜索互联网，我找不到任何讨论实现一个可变数组作为一个树。
编辑:简短的回答:似乎NSMutableArray是作为一个循环缓冲区实现的，所以这个问题没有意义。如果有一个优势实现一个数组作为一个2-3树，我仍然想知道它。
Bartosz Ciechanowski在他的博客文章" exposed nsmutablearray "
中给出了令人难以置信的详细答案。tl;dr:这是一个"循环缓冲区":"
数据结构你可能已经猜到了，__NSArrayM使用循环缓冲区。这种数据结构非常简单，但比常规的数组/缓冲区要复杂一些。当到达循环缓冲区的任意一端时，循环缓冲区的内容都可以绕回。
循环缓冲区有一些非常酷的属性。值得注意的是，除非缓冲区已满，否则从任何一端插入/删除都不需要移动任何内存。让我们来分析一下，与C数组相比，这个类是如何利用循环缓冲区在其行为上取得优势的。
从历史上看，__NSArrayM是一个比cocoa更新的类名——它在OSX 10.0中没有这样叫，但我找不到旧名字的好链接。也许它以前是一棵树。你第一个评论中的链接让它听起来像在2005年，在大尺寸它不是一个循环缓冲区内部。